ソートされたダブルリンクリスト挿入の再帰

Question

私はデータ構造と再帰の概念が初めてです。私はなぜこのコンセプトで再帰を使用できるのかを理解するのに苦労しています。私はこのコードをフォーラムで見つけました。このコンセプトは本当に理解できませんでした。 2 1 3 4の単純なケースの場合、いずれかが反復ステップを説明できる場合は、私のために大きく評価されます。 https://www.hackerrank.com/challenges/insert-a-node-into-a-sorted-doubly-linked-list

Node SortedInsert(Node head,int data) { 
    Node n = new Node(); 
    n.data = data; 
    if (head == null) { 
     return n; 
    } 
    else if (data <= head.data) { 
     n.next = head; 
     head.prev = n; 
     return n; 
    } 
    else { 
     Node rest = SortedInsert(head.next, data); 
     head.next = rest; 
     rest.prev = head; 
     return head; 
    } 
} 

Answer 1

再帰：ここ

がハッカーのランクのためのリンクがある 再帰関数は自分自身を呼び出すこと。これは、複数の状態（通常は多数の状態）を保存し、それらを逆の順序で取得する必要があるアルゴリズムの状態情報を保存する簡単な方法として使用されます。 （プログラムの状態を保存するためにStackオブジェクトを使用するなど、より専門的で、メモリの問題を起こしにくい代替テクニックがあります）。

この例は貧弱ですが、再帰のイントロの典型です。はい、再帰を使用してリンクされたリストを反復できますが、絶対に理由はありません。ループがより適切です。これは純粋に再帰がどのように機能するかを実証するためのものです。だから、あなたの質問に答えるのはなぜですか？それは単純に概念を学び、後に実際に理にかなった他のアルゴリズムで使用することができます。

再帰は、リンクされたリストではなく、各ノードが複数の他のノードを指すツリーを持つ場合に便利です。その場合、リンクされたノードの1つをトラバースして戻って次のノードに進むことができるように、状態（現在のノードと最後に呼び出したサブノード）を保存する必要があります。

あなたはまた、「どのように」尋ねました。関数が自身を呼び出すと、その変数はすべて（プログラムスタック上に）保存され、次の繰り返しのために新しい変数が作成されます。次に、その呼び出しが返ってくると、呼び出された場所に戻り、以前の変数のセットがロードされます。これは、変数の同じコピーが毎回使用される "ジャンプ"や何らかのループとはまったく異なります。再帰を使用すると、呼び出されるたびにすべてのローカル変数の新しいコピーが作成されます。これは、この例では決して変化しない "データ"変数であっても当てはまります（したがって、1つの非効率性）。