Understanding Recursion / how are subproblems combined (Max-Subarray Algorithm)

Question

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.

So I'm given the following recursive algorithm of finding a maximum subarray in pseudocode:

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 >= right-sum and left-sum >= cross-sum
        return (left-low, left-high, left-sum)
    else if right-sum >= left-sum and right-sum >= cross-sum
        return (right-low, right-high, right-sum)
    else
        return (cross-low, cross-high, cross-sum)

where the Find-Max-Crossing-Subarray algorithm is given by the following pseudocode:

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 > 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 > right-sum 
        right-sum = sum
        max-right = j
return (max-left, max-right, left-sum + right-sum)

Now when I try to apply this algorithm to an example, I'm having a hard time understanding all the steps.

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.

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?

My answer in another thread might help you out. It goes pretty far in depth of a good recursion example. — user3507600
– user3507600, Commented Apr 15, 2014 at 16:30

AbcAeffchen · Accepted Answer · 2015-08-10 10:38:07Z

2

In short:
Let A be an array of length n. You want to compute the max subarray of A sou you call Find-Maximum-Subarray(A, 0, n-1). Now try to make the problem easier:

Case. high = low:
In this case the Array has only 1 Element so the solution is simple
high != low
In this case the solutions are to hard to find. so try to make the problem smaller. What happens if we cut the array A into arrays B1 and B2 of the half length. Now there are only 3 new cases

a) the Max Subarray of A is also a subarray of B1 but not of B2
b) The max subarray of A is also a subarray of B2 but not of B1
c) The max subarray of A overlaps with B1 and B2

so you compute the max subarray of B1 and B2 separately and look for an overlapping solution and finally you take the largest one.

The trick is now, that you can du the same thing with B1 and B2.

Example:

A =[-1, 2, -1, 1]
Call Find-Maximum-Subarray(A, 0, 3);
 - Call Find-Maximum-Subarray(A, 0, 1); -> returns ( 1, 1, 2 )  (cause 2 > 1 > -1,  see the subcalls)
    - Call Find-Maximum-Subarray(A, 0, 0); -> returns ( 0, 0, -1 )
    - Call Find-Maximum-Subarray(A, 1, 1); -> returns ( 1, 1, 2 )
    - Call Find-Max-Crossing-Subarray(A, 0, 0, 1); -> returns ( 0, 1, 1 )
 - Call Find-Maximum-Subarray(A, 2, 3); -> returns ( 3, 3, 1 ) ( 1 > 0 > -1, see subcalls)
    - Call Find-Maximum-Subarray(A, 2, 2); -> returns ( 2, 2, -1 )
    - Call Find-Maximum-Subarray(A, 3, 3); -> returns ( 3, 3, 1 )
    - Call Find-Max-Crossing-Subarray(A, 2, 2, 3); returns ( 2, 3, 0 )
 - Call Find-Max-Crossing-Subarray(A, 0, 1, 3); -> returns ( 1, 3, 2 )
    - Here you have to take at least the elements A[1] and A[2] with the sum of 1, 
      but if you also take A[3]=1 the sum will be 2. taking A[0] does not help 
      due to A[0] is negative
 - Now you have only to look which subarray has the larger sum. In this case you 
   have two with the same size: A[1] and A[1-3]. Return one of them.

edited Aug 10, 2015 at 10:38

answered Apr 15, 2014 at 17:50

AbcAeffchen

15.1k15 gold badges52 silver badges67 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

eager2learn Over a year ago

I understand that. What I don't understand is how we get from the solution of the base case to the solutions of subarrays of length 2 and eventually of the full array. So e.g. if I call Find-Maximum-Subarray we will eventually, as the recursion bottoms out, get subarrays of length 1. Now how does this algorithm use the results of the base case? That seems like magic to me. Where does the computer store these base case results and where in the algorithm are the functions with the results of the base cases called?

AbcAeffchen Over a year ago

I added an example for length 4

eager2learn Over a year ago

Thanks a ton, that's exactly what I wanted to know. You helped me a lot, I appreciate your effort.

Collectives™ on Stack Overflow

Understanding Recursion / how are subproblems combined (Max-Subarray Algorithm)

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related