リンクされたリスト要素を逆順に印刷する際に、再帰はどのように機能しますか？

Question

私は再帰がどのように機能するか少し考えています。以前に呼び出された関数によって返された値を格納するために使用されるスタックによって提供される変数に関する呼び出しと異なるコンテキスト。この再帰関数で

例えば、

void Factorial(int n) 
{ 
    if(n==0) return 0; 
    else if(n==1) return 1; 
    else 
    { 
    return n*Factorial(n-1); 
    } 
} 

所定数の階乗を計算するため、私は、与えられたNを想定するための最初の呼び出しは、5である5 *階乗（4 *階乗（あろうことを知っています3 ...などの基本条件に達するまで）、1 * 2 * 3 * 4 * 5 = 240のような値を合計した順番にトラバースします。

私が理解していないのは、単一リンクリストの項目を逆順に印刷するコードです。

void ReversePrint(Node head) {  
if(head==null) 
    { 
    return; 
    } 
else 
    { 
    ReversePrint(head.next); 
    System.out.println(head.data); 
    } 
} 

限りヘッドは、それが他の状態に行くと頭が対等になるnullではないので、私は、リンクリスト機能のような作品に有限個の要素がある

まず

、 を与え知っているようにそれがnullになるまでhead.nextに移動します。そして何？

私は正確な言葉で私の問題を表現していないかもしれません。あなたが説明することを願っています。前もって感謝します。

Answer 1

いくつかの余分なコメントが助けるべき追加：

void ReversePrint(Node node) { 
    if (node == null) { 
     // An empty list has nothing to print. 
     return; 
    } else { 
     // First print the rest of the list. 
     ReversePrint(node.next); 
     // Then print this node. 
     System.out.println(node.data); 
    } 
} 

ので - 基本的に -

• 空のリストには何も出力しません。
• 空でないリストは、残りのリストを印刷する必要があります。最初にを印刷し、ルートノードを出力します。

リストが後ろに印刷されています。

Answer 2

ReversePrintRestという名前の関数があり、リストをとり、すべてをであるが、の頭を逆にして印刷したとします。そして、あなたは非常に簡単にReversePrintを書くことができます：

void ReversePrint(Node head) {  
    if(head==null) { 
     return; 
    } else { 
     ReversePrintRest(head); 
     System.out.println(head.data); 
    } 
} 

限りReversePrintRestとして作品宣伝として、私はあなたが、これが機能することを合意するには問題がないと仮定します。 ReversePrintRestを記述する方法については

、それも簡単です：

再び

void ReversePrintRest(Node head) { 
    ReversePrint(head.next); 
} 

、ReversePrint作品、正しさも見やすいと仮定。 ReversePrintRestの本文は元のコードから直接取得されているため、元のコードも正しいはずです。

これは少し難解なように見えるかもしれません。各機能の正確さは、他の機能によって異なります。しかし、我々はReversePrintについて、もう少し明確にすることができます：それは明らかにそれは短いリストのために働くことをを想定すると、空のリスト

のために働く

• 、それが仕事に知られているコードに依存することによって、現在の1のために働きますより短いリストでそれを使って正しいことをする（すなわち、残りを逆印刷した後にヘッドを印刷する）。
  • 我々は、それが空のリストのために働くので、それは長さ1のリストのために働く空のリスト
  • の作品を知っている：正当化するだけの仮定を残し

  。

• これはlength-1リストで機能するため、length-2リストで機能します。

となります。長さNのリストが必要な場合は、そのロジックに従うことができます。引数はNの特定の値に依存しないので、すべての値に適用されます。

Answer 3

おそらくこの質問に重複がありますが、それらを見つけてリンクするのではなく、私があなたが求めているものに問題があるものに取り組んでいきたいと思います。

階乗の例では、通常、非常に高い階乗を計算したくないため、再帰がうまく動作します。もしそうしたいのであれば、スタックオーバーフローを起こす前に通常は整数オーバーフローになります。

しかし、リストは非常に一般的に1000個以上の要素サイズです。私の実装では、ReversePrintメソッドはStackOverflowErrorを約10000要素以上のリンクリストにしました。これは、Javaがメモリ内のスタックサイズを制限するためです。このようなアプリケーションのために

が、このようなものを使用することにより、非再帰的にそれを行うにははるかに優れている：いくつかの追加機能は、このような何かを完了するために必要な

ReversePrint(YourList l) { 
    Node n = l.last; 
    while (n != null) { 
     System.out.println(n.data); 
     n = n.prev; 
    } 
} 

注こと。リストは前方リンクと後方リンクの両方にリンクされていなければならず、単純化するために、すべてをカプセル化するための何らかの種類のYourListクラスがなければなりません。