title: recursive size method linked list
body: <p>I am trying to understand the output I am receiving from my rercusive linked list size method.</p>
  
  <pre><code>private int size(Node list)
  {
     if (list == null)   
         return 0;
     else 
     {
        int results = size(list.next) + 1; 
        System.out.println(results);
        return results;
     }             
  }
  </code></pre>
  
  <p>The output I receive as it runs is this:</p>
  
  <blockquote>
    <p>1
    2
    1
    2
    3
    1
    2
    3
    1
    2
    3
    1
    2
    3
    4
    1
    2
    3
    4
    1
    2
    3
    4
    1
    2
    3
    4
    1
    2
    3
    4
    1
    2
    3
    4
    5</p>
  </blockquote>
  
  <p>It calculates the right answer, but it produces more recursive calls than I was expecting. I was expecting an output that would look like this.</p>
  
  <blockquote>
    <p>1
    2
    3
    4
    5</p>
  </blockquote>
  
  <p>Why is this?</p>
  
  <p>I noticed when I add elements this way <code>ll.add("Amy"); ll.add("Bob")</code> I receive the output I was expecting, but when I add elements this way <code>ll.add(0, "Al"), ll.add(2, "Beth"), ll.add(4, "Carol")</code> it produces the output I wasn't expecting. I am trying to figure out why the output looks like this, any ideas?</p>
  
  <pre><code> public static void main(String [] args)
   {
      RLinkedList ll = new RLinkedList();
      ll.add("Amy");
      ll.add("Bob");
      ll.add(0, "Al");
      ll.add(2, "Beth");
     ll.add(4, "Carol");
      System.out.println(ll.size());
  </code></pre>
  
  <p>This is the recursive add methods I am using.</p>
  
  <pre><code>public void add(String e)
  {
     // Replace first with result of adding e to first 
     first = add(e, first);
  }
  
  /**
     This recursive private add method adds
     an element e to the end of a list.
     @param e The element to add to the list.
     @param list The list to add e to.
     @return The list resulting from adding e to its end.
  */
  
  private Node add(String e, Node list)
  {
     if (list == null)
     {
         // Base case
         return new Node(e);
     }
     else
     {
         // Add e to the end of the tail and use
         // the result to replace the tail
         list.next = add(e, list.next);
         return list;
     }        
  }
  
  /**
     The add method adds an element e at place index
     in this linked list.
     @param index The place in the list to add an element.
     @param e The element to add this the linked list.
       @exception IndexOutOfBoundsException When index is 
                out of bounds.  
  */
  
  public void add(int index, String e)
  {
     // Replace first with the result of adding
     // e at index in first
     first = add(index, e, first);        
  }    
  
  /**
     This add method adds an element at an index in a list.
     @param e The element to add to the list.
     @param index The index at which to add the element.
     @param list The list to add e to.
     @return The list resulting from adding e.
     @exception IndexOutOfBoundsException When index is 
                out of bounds.  
  */
  
  private Node add(int index, String e, Node list)
  {
      if (index &lt; 0  || index &gt; size()) 
      {
           String message = String.valueOf(index);
           throw new IndexOutOfBoundsException(message);
      }         
      if (index == 0)        
           return new Node(e, list);        
  
      // 0 &lt; index and index &lt;= size so list is not empty
      // Replace the tail with result of adding e at index - 1
      // in the tail
  
      list.next = add(index-1, e, list.next);        
      return list;     
  </code></pre>
  
  <p>This is the Node class</p>
  
  <pre><code>private class Node
  {
      String value;   
      Node next;      
  
      /**
         Constructor.            
         @param val The element to store in the node.
         @param n The reference to the successor node.
      */
  
      Node(String val, Node n)
      {
          value = val;
          next = n;
      } 
  
      /**
         Constructor. 
         @param val The element to be stored in the node.
      */
  
      Node(String val)
      {
         // Just call the other (sister) constructor
         this(val, null);            
      }
  }   
  </code></pre>