title: Understanding Recursion / how are subproblems combined (Max-Subarray Algorithm)
body: <p>I'm having some problems understanding divide and conquer algorithms. I've read that in order to apply recursion successfully you need to have a "recursive leap of faith" and you shouldn't bother with the details of every step, but I'm not really satisfied with just accepting that recursion works if all the conditions are fulfilled, because it seems like magic to me at the moment and I want to understand why it works.</p>
  
  <p>So I'm given the following recursive algorithm of finding a maximum subarray in pseudocode:</p>
  
  <pre><code>Find-Maximum-Subarray(A, low, high)
  if high == low
      return (low, high, A[low])
  else
      mid = [(low + high)/2]
      (left-low, left-high, left-sum) = Find-Maximum-Subarray(A, low, mid)
      (right-low, right-high, right-sum) = Find-Maximum-Subarray(A,mid + 1, high)
      (cross-low, cross-high, cross-sum) = Find-Max-Crossing-Subarray(A,low, mid, high)
      if left-sum &gt;= right-sum and left-sum &gt;= cross-sum
          return (left-low, left-high, left-sum)
      else if right-sum &gt;= left-sum and right-sum &gt;= cross-sum
          return (right-low, right-high, right-sum)
      else
          return (cross-low, cross-high, cross-sum)
  </code></pre>
  
  <p>where the Find-Max-Crossing-Subarray algorithm is given by the following pseudocode:</p>
  
  <pre><code>Find-Maximum-Crossing-Subarray(A, low, mid, high)
  left-sum = -INF
  sum = 0
  for i = mid down to low
      sum = sum + A[i]
      if sum &gt; left-sum
          left-sum = sum
          max-left = i
  right-sum = -INF
  sum = 0
  for j = mid + 1 to high
      sum = sum + A[j]
      if sum &gt; right-sum 
          right-sum = sum
          max-right = j
  return (max-left, max-right, left-sum + right-sum)
  </code></pre>
  
  <p>Now when I try to apply this algorithm to an example, I'm having a hard time understanding all the steps.</p>
  
  <p>The array is "broken down" (using the indices, without actually changing the array itself) until high equals low. I thinks this corresponds to the first call, so Find-Maximum-Subarray is first called for all the terms on the left of the array, until high==low==1. Then (low, high, A[low]) is returned which would be (1, 1, A[1]) in this case. Now I don't understand how those values are processed in the remainder of the call.</p>
  
  <p>Furthermore I don't understand how the algorithm actually compares subarrays of lengths > 1. Can anybody explain to me how the algorithm continues once one of the calls of the function has bottomed out, please?</p>