リンクリストの最後にノードを挿入

Question

このような問題には単純な反復解があります。

Node Insert(Node head,int data) { 
    Node newNode = new Node(); 
    newNode.data = data; 
    if (head == null) { 
     return newNode; 
    } 
    Node current = head; 
    while (current.next != null) { 
     current = current.next; 
    } 
    current.next = newNode; 
    return head; 
} 

それは完全に正常に動作します。しかし、私は再帰を学び、その視点で物事を見たいと思っています。したがって、私は下の解決策を思いついた、それはエレガントだが、私はそれがちょうど直感と与えられたコードが働いたことを認めなければならない。私は再帰や少なくとも私のコードがうまく動作することを確認するためのいくつかの方法で作業するためのメンタルモデルを開発したい。理論的には、以下の解決策が有効であることを検証する方法。

私はほんの少しの更なるコードを取ると、複数の出口ポイントを削除します

Node Insert(Node head,int data) { 
    // Base case. 
    if (head == null) { 
     Node newNode = new Node(); 
     newNode.data = data; 
     return newNode; 
    } 
    // Smaller problem instance. 
    head.next = Insert(head.next, data); 
    return head; 
} 

Answer 1

再帰バージョン。これにより、リストへの影響と返されるノードmutの両方について推論することができます。

Node appendRecursive(Node head, int data) { 
    // By default return the same list we were given. 
    Node list = head; 
    if (list == null) { 
     // At end of list or list is empty. 
     list = new Node(); 
     list.data = data; 
    } else { 
     // Recurse. 
     head.next = appendRecursive(head.next, data); 
    } 
    return list; 
} 

は限り推論が行くように、あなたは一般的に誘導を使用する必要があります。

• リストが空の場合（list == null）、新しいノードを作成し、これがリストになります。
• リストが空でない場合、新しいリストは、新しいデータが追加されたリストでなければなりません。

上記を前提とすると、リストが空であるかそうでないかのいずれかが原因で、これが正しく機能するという理由が考えられる可能性があります。

リスト上での再帰の使用は、反復アルゴリズムが線形構造とよく適合するため、一般的に非効率的で厄介なものとみなされます。より良いエクササイズは、自分自身のTree構造体を書くことです。なぜなら、ツリーは再帰的アルゴリズムに非常によく役立つからです。ツリー上で必要な関数を再帰的に実行する方がはるかに簡単で洗練されていることがわかります。

static class Tree { 

    Node head = null; 

    class Node { 

     Node left; 
     Node right; 
     int data; 

     private Node(int data) { 
      this.data = data; 
     } 
    } 

    void insert(int data) { 
     head = insert(head, data); 
    } 

    private Node insert(Node node, int data) { 
     if (node == null) { 
      // Empty tree becomes just the node. 
      return new Node(data); 
     } else { 
      // Pick the correct branch to add this data to. 
      if (data < node.data) { 
       node.left = insert(node.left, data); 
      } else { 
       node.right = insert(node.right, data); 
      } 
     } 
     return node; 
    } 

    private CharSequence toString(Node n) { 
     StringBuilder s = new StringBuilder(); 
     if (n != null) { 
      // First print the tree on the left. 
      if (n.left != null) { 
       s.append(toString(n.left)).append(","); 
      } 
      // Then the data in this node. 
      s.append(n.data); 
      // Then the tree on the right. 
      if (n.right != null) { 
       s.append(",").append(toString(n.right)); 
      } 
     } 
     return s; 
    } 

    @Override 
    public String toString() { 
     // Even toString is recursive. 
     StringBuilder s = new StringBuilder("{"); 
     s.append(toString(head)); 
     return s.append("}").toString(); 
    } 
} 

public void test() { 
    Tree tree = new Tree(); 
    for (int i : new int[]{6, 5, 4, 3, 2, 1}) { 
     tree.insert(i); 
    } 
    System.out.println(tree); 
} 

toString方法で、それはどこに追加するに判断するのがいかに簡単なお知らせ「」 - 悪名高い不格好な問題のリストを印刷します。

Answer 2

Node Insert(Node head,int data) { 
    if (head == null) { 
     head = new Node(); 
     head.data = data; 
    } 
    else{ 
    head.next = Insert(head.next, data); 
    } 
    return head; 
} 

あなたは5,3,2,1を持っていて、その後、4を追加したいと仮定します - node(3)とInsert(node(3),4)を呼んでいるhead.next = node(5).nextなし、その後

if(node(5) == null)（4 int型、ノード（5））を挿入しません

if(node(3) == null)ない次いでnode(2)とhead.next = node(2).nextワット何次いでInsert(node(2),4)

if(node(2) == null)を呼び出していないhead.next = node(3).next HICHはnode(1)で、「何の要素がnode(1)後がないので」nullです、はい、その後head = new node();を設定し、エンド・リターンヘッドでデータhead = new node();を設定Insert(node(1).next,4)

(node(1).next) == nullを呼んでhead.next = node(1).nextなし、その後Insert(node(1),4)

if( node(1) == null)を呼び出していません

Answer 3

一般的に、再帰的解は次の規則に従わなければなりません。

1. 一般の場合との場合の場合を区別しなければなりません。ベースブロックと、一般的なブロック：そして、それは2つのコードブロックにコード分岐（典型的には1 if）のいくつかのタイプを含む必要があります。
2. ベースブロックは、即時応答（再帰的ではない）を返す必要があります。
3. 一般ブロックは同じ関数を（再帰的に）再呼び出しする必要がありますが、同じ引数値（無限再帰を生成します）ではなく、の値を基底ケースに転送します（）。

これは単純な再帰モデルであり、実際にはもっと複雑になることがあります（複数の基本ケース、2つの関数間の再帰など）。

我々はこれらの規則に従って、理論的にはあなたの提案を分析する場合、我々はそれがそれらのすべてを満たしている見ることができます。