title: Insert node at the end of linked list
body: <p>There is a simple iterative solution for these kind of problems.</p>
  
  <pre><code>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;
  }
  </code></pre>
  
  <p>It works perfectly fine. But I want to learn recursion and see the things with that perspective. Hence I came up with the below solution, it seems elegant but I have to admit that it was just <strong>intuition</strong> and the given code worked. I want to develop a mental model for working with recursion or at least some way to verify that my code will work fine. How to verify theoretically that the below solution should work. </p>
  
  <p>Recursive version</p>
  
  <pre><code>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;
  }
  </code></pre>