recursive size method linked list
<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>