title: Understanding double recursion
body: <p>I'm able to comprehend recursion easily if there is just one recursive call within a function. However, I am really getting confused when I see two or more recursive calls within the same function. Example:</p>
  
  <pre><code>int MaximumElement(int array[], int index, int n)
      {  
          int maxval1, maxval2; 
          if ( n==1 ) return array[index];
          maxval1 = MaximumElement(array, index, n/2); 
          maxval2 = MaximumElement(array, index+(n/2), n-(n/2));
          if (maxval1 &gt; maxval2)
              return maxval1;
          else
              return maxval2;
      }
  </code></pre>
  
  <p>I understand one thing that n gets decremented by half during each recursive call. I just don't understand how the next recursive call works. It gets confusing and my understanding until that point falls apart and I give up. I would be really thankful if somebody could please illustrate this manually with a neat example. I already did the programming, and printed the outputs. However, I don't understand how the calculations behind this work. Here is my understanding until the point where everything gets to nothing:</p>
  
  <p>int a[] = {1,2,10,15,16,4,8}</p>
  
  <p>Initial call: MaximumElement(a, 0, 7)</p>
  
  <p>The function begins:
  First call: MaximumElement(a, 0, 7/2)
  n now becomes 7/2 = 3</p>
  
  <p>Second Call: MaximumElement(2,0,3/2)
  n now becomes 3/2 = 1</p>
  
  <p>The base condition is met and the max1 gets a[0] = 1</p>
  
  <p>Here is where all hell breaks loose:
  The second recursive call begins with index 0 and n = index + n/2 = 0 + 1/2 = 0? When I print the values the program shows 3 as the value for n when the second call is being made.</p>
  
  <p>I have programmed extensively, but I am really having a nightmare with this. Many thanks to somebody that can break this down for me!!</p>
  
  <p>That was the pseudocode above, but see below for the java code I wrote (it might make it easier for you if you are trying to run it):</p>
  
  <pre><code>        public int MAXIMUMELEMENT(int a[], int i, int n)
          {
          int max1, max2;
  
          System.out.println("1: " + i + " 2: " + n);
  
          if(n == 1)
          {
              System.out.println("Returning " + a[i]);
          return a[i];
          }
  
  
  
          max1 = MAXIMUMELEMENT(a, i, n/2);
  
          System.out.println("Index: "+i+" "+" Variable: "+max1+" n value: "+n);
  
  
              max2 = MAXIMUMELEMENT(a, i + (n/2), n - (n/2));
  
          System.out.println("Index2: " + i + " " + "Variable2: " + max2);
  
  
          if(max1 &gt; max2)
          {
              System.out.println("Returning.... " + max1 );    
                  return max1;
          }
          else
          {
          System.out.println("Returning.... " + max2);     
          return max2;
          }
  }
  </code></pre>