What how does the base case work in this recursion program?

There is a simple program in my textbook that I pasted below. There is a method in the program that takes an array, divides it evenly into two arrays, and recursively passes each half-array back into the method until it reaches the base case. Then, the program figures out what the biggest subsequence is in each half-array, considering that the subsequence MUST touch the center divider. In other words, anything this program sums up must include either -2 or -1 from myArray below.

For-yan, or anyone, can you explain to me what is happening to the half-arrays in line 24 and 25? Specifically, I want to know how the recursion stops and what the arrays look like when the recursion is done. Please do not make more than 1 post if possible, and don't include any information that's not related to my question about lines 24 and 25. Thanks very much!
public class SplitSubsequence {

    public static void main(String[] args) {
        int[] myArray = {4,-3,5,-2,-1,2,6,-2};
        System.out.println(maxSumRec(myArray, 0, myArray.length -1));

    }


/**
     * Recursive maximum contiguous subsequence sum algorithm.
     * Finds maximum sum in subarray spanning a[left..right].
     * Does not attempt to maintain actual best sequence.
     */
    private static int maxSumRec( int [ ] a, int left, int right )
    {
        int maxLeftBorderSum = 0, maxRightBorderSum = 0;
        int leftBorderSum = 0, rightBorderSum = 0;
        int center = ( left + right ) / 2;

        if( left == right )  // Base case
            return a[ left ] > 0 ? a[ left ] : 0;

        int maxLeftSum  = maxSumRec( a, left, center );
        int maxRightSum = maxSumRec( a, center + 1, right );

        for( int i = center; i >= left; i-- )
        {
            leftBorderSum += a[ i ];
            if( leftBorderSum > maxLeftBorderSum )
                maxLeftBorderSum = leftBorderSum;
        }

        for( int i = center + 1; i <= right; i++ )
        {
            rightBorderSum += a[ i ];
            if( rightBorderSum > maxRightBorderSum )
                maxRightBorderSum = rightBorderSum;
        }

        return maxLeftSum + maxRightSum;
    }

}

Open in new window

shampouyaAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

for_yanCommented:
I don't think anything happnes to the array in  all this process I don't see any assignemnt to array elemnts - array
stays the same - you just change the second and third arguments specifying differnt protions
so when you both arguments second and third becomes equal then you return this elemnt of the array or zero if it is negative
0
shampouyaAuthor Commented:
Oh ok, you're right, the array doesn't change. By the way, I made a mistake; line 41 of the code above should read return maxLeftBorderSum + maxRightBorderSum. I added the wrong variables.

The result of this program is 11 if you make the correction on line 41. Can you type for me the numbers that were added out of {4,-3,5,-2,-1,2,6,-2} BEFORE arriving at the answer of 11? In other words, I want to know in chronological order what the program is adding, step by step arithmetic, before getting the final answer of (4+(-3)+5+(-2)) + (-1+2+6) = 11
0
for_yanCommented:
One post ort not one post , I prefer to post something which I think should help to understand.

So execute the code where I added some printout (or look at its output at the bottom)
and you'll see that array on all iterations remains the same, so neither at lines 24,25 or at any other lines
nothing is being changed in the array:

public class SplitSubsequence {

    static int count = 0;
    public static void main(String[] args) {
        int[] myArray = {4,-3,5,-2,-1,2,6,-2};
        System.out.println(maxSumRec(myArray, 0, myArray.length -1));

    }


/**
     * Recursive maximum contiguous subsequence sum algorithm.
     * Finds maximum sum in subarray spanning a[left..right].
     * Does not attempt to maintain actual best sequence.
     */
    private static int maxSumRec( int [ ] a, int left, int right )
    {

         System.out.print(" printing arry for the " + count + " th time:  ");
        count++;
        for (int ii: a){
            System.out.print(ii + ",");

        }
        System.out.println(" ");
          
        

        int maxLeftBorderSum = 0, maxRightBorderSum = 0;
        int leftBorderSum = 0, rightBorderSum = 0;
        int center = ( left + right ) / 2;

        if( left == right )  // Base case
            return a[ left ] > 0 ? a[ left ] : 0;

        int maxLeftSum  = maxSumRec( a, left, center );
        int maxRightSum = maxSumRec( a, center + 1, right );

        for( int i = center; i >= left; i-- )
        {
            leftBorderSum += a[ i ];
            if( leftBorderSum > maxLeftBorderSum )
                maxLeftBorderSum = leftBorderSum;
        }

        for( int i = center + 1; i <= right; i++ )
        {
            rightBorderSum += a[ i ];
            if( rightBorderSum > maxRightBorderSum )
                maxRightBorderSum = rightBorderSum;
        }

        return maxLeftSum + maxRightSum;
    }

}

Open in new window



printing arry for the 0 th time:  4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 1 th time:  4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 2 th time:  4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 3 th time:  4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 4 th time:  4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 5 th time:  4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 6 th time:  4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 7 th time:  4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 8 th time:  4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 9 th time:  4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 10 th time:  4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 11 th time:  4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 12 th time:  4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 13 th time:  4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 14 th time:  4,-3,5,-2,-1,2,6,-2, 
17

Open in new window

0
Cloud Class® Course: Ruby Fundamentals

This course will introduce you to Ruby, as well as teach you about classes, methods, variables, data structures, loops, enumerable methods, and finishing touches.

shampouyaAuthor Commented:
Could you explain the same thing using this code (the result should be 11 not 17):

public class SplitSubsequence {

    public static void main(String[] args) {
        int[] myArray = {4,-3,5,-2,-1,2,6,-2};
        System.out.println(maxSumRec(myArray, 0, myArray.length -1));

    }


/**
     * Recursive maximum contiguous subsequence sum algorithm.
     * Finds maximum sum in subarray spanning a[left..right].
     * Does not attempt to maintain actual best sequence.
     */
    private static int maxSumRec( int [ ] a, int left, int right )
    {
        int maxLeftBorderSum = 0, maxRightBorderSum = 0;
        int leftBorderSum = 0, rightBorderSum = 0;
        int center = ( left + right ) / 2;

        if( left == right )  // Base case
            return a[ left ] > 0 ? a[ left ] : 0;

        int maxLeftSum  = maxSumRec( a, left, center );
        int maxRightSum = maxSumRec( a, center + 1, right );

        for( int i = center; i >= left; i-- )
        {
            leftBorderSum += a[ i ];
            if( leftBorderSum > maxLeftBorderSum )
                maxLeftBorderSum = leftBorderSum;
        }

        for( int i = center + 1; i <= right; i++ )
        {
            rightBorderSum += a[ i ];
            if( rightBorderSum > maxRightBorderSum )
                maxRightBorderSum = rightBorderSum;
        }

        return maxLeftBorderSum + maxRightBorderSum;
    }

}

Open in new window

0
for_yanCommented:
public class SplitSubsequence {

    static int count = 0;
    public static void main(String[] args) {
        int[] myArray = {4,-3,5,-2,-1,2,6,-2};
        System.out.println(maxSumRec(myArray, 0, myArray.length -1, "first call"));

    }


/**
     * Recursive maximum contiguous subsequence sum algorithm.
     * Finds maximum sum in subarray spanning a[left..right].
     * Does not attempt to maintain actual best sequence.
     */
    private static int maxSumRec( int [ ] a, int left, int right, String which )
    {
               System.out.print(" printing arry for the " + count + " th time   " + which + ": ");
                count++;
                for (int ii: a){
                                System.out.print(ii + ",");

                }
                System.out.println(" ");




        int maxLeftBorderSum = 0, maxRightBorderSum = 0;
        int leftBorderSum = 0, rightBorderSum = 0;
        int center = ( left + right ) / 2;

        if( left == right ) {
            System.out.println(" returning from base case " + which + " " + a[left] ); // Base case
            return a[ left ] > 0 ? a[ left ] : 0;
        }

        int maxLeftSum  = maxSumRec( a, left, center, "first call" );
        int maxRightSum = maxSumRec( a, center + 1, right, "second call" );

        for( int i = center; i >= left; i-- )
        {
            leftBorderSum += a[ i ];
            if( leftBorderSum > maxLeftBorderSum )
                maxLeftBorderSum = leftBorderSum;
        }

        for( int i = center + 1; i <= right; i++ )
        {
            rightBorderSum += a[ i ];
            if( rightBorderSum > maxRightBorderSum )
                maxRightBorderSum = rightBorderSum;
        }

         System.out.println(" returning from the bottom " + which +  " " +  (maxLeftBorderSum + maxRightBorderSum));
        return maxLeftBorderSum + maxRightBorderSum;
    }

}

Open in new window


Output:
 printing arry for the 0 th time   first call: 4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 1 th time   first call: 4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 2 th time   first call: 4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 3 th time   first call: 4,-3,5,-2,-1,2,6,-2, 
 returning from base case first call 4
 printing arry for the 4 th time   second call: 4,-3,5,-2,-1,2,6,-2, 
 returning from base case second call -3
 returning from the bottom first call 4
 printing arry for the 5 th time   second call: 4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 6 th time   first call: 4,-3,5,-2,-1,2,6,-2, 
 returning from base case first call 5
 printing arry for the 7 th time   second call: 4,-3,5,-2,-1,2,6,-2, 
 returning from base case second call -2
 returning from the bottom second call 5
 returning from the bottom first call 6
 printing arry for the 8 th time   second call: 4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 9 th time   first call: 4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 10 th time   first call: 4,-3,5,-2,-1,2,6,-2, 
 returning from base case first call -1
 printing arry for the 11 th time   second call: 4,-3,5,-2,-1,2,6,-2, 
 returning from base case second call 2
 returning from the bottom first call 2
 printing arry for the 12 th time   second call: 4,-3,5,-2,-1,2,6,-2, 
 printing arry for the 13 th time   first call: 4,-3,5,-2,-1,2,6,-2, 
 returning from base case first call 6
 printing arry for the 14 th time   second call: 4,-3,5,-2,-1,2,6,-2, 
 returning from base case second call -2
 returning from the bottom second call 6
 returning from the bottom second call 8
 returning from the bottom first call 11
11

Open in new window

0
for_yanCommented:
when you call recusrive method twice in the body it really becomes difficult to understand
0
shampouyaAuthor Commented:
Yeah the recursion part is confusing. Am I right in saying that the program analyzes the array as two pieces, and then with four pieces, and eventually with eight pieces, and that's when the recursion stops?
0
for_yanCommented:


go to this link:
http://cs.unomaha.edu/~stanw/021/3320/m02.pdf

and on page 2 in boxes labeled "Algorithm 3" they give detailed
explanation of how this thing works
0
shampouyaAuthor Commented:
Algorithm 3 on page 2 explains the logic but it doesn't explain the recursion. In the code from my example, it appears that the 8-element array is being organized into two sections, the first half and the second half. But then those two half sections of the array are each passed back into the maxSumRec() method, which means that the 8-element array is now being analyzed in 4 sections of two elements. And finally with the last round of recursion, the 8-element array is analyzed as 8 sections, each with 1 element, and that's when the recursion stops and the program commences the for loops. Am I correct that the recursion organizes this array into 8 sections?
0
for_yanCommented:

and you know what - the code you posted is not correct.
This is the correct one:
Looke here:
http://www.java-tips.org/java-se-tips/java.lang/finding-maximum-contiguous-subsequence-sum-using-divide-and-conquer-app.html

  private static int maxSumRec( int [ ] a, int left, int right )
  {
        int maxLeftBorderSum = 0, maxRightBorderSum = 0;
        int leftBorderSum = 0, rightBorderSum = 0;
        int center = ( left + right ) / 2;

        if( left == right )  // Base case
            return a[ left ] > 0 ? a[ left ] : 0;

        int maxLeftSum  = maxSumRec( a, left, center );
        int maxRightSum = maxSumRec( a, center + 1, right );

        for( int i = center; i >= left; i-- )
        {
            leftBorderSum += a[ i ];
            if( leftBorderSum > maxLeftBorderSum )
                maxLeftBorderSum = leftBorderSum;
        }

        for( int i = center + 1; i <= right; i++ )
        {
            rightBorderSum += a[ i ];
            if( rightBorderSum > maxRightBorderSum )
                maxRightBorderSum = rightBorderSum;
        }

        return max3( maxLeftSum, maxRightSum,
                     maxLeftBorderSum + maxRightBorderSum );
    }

    /**
     * Return maximum of three integers.
     */
    private static int max3( int a, int b, int c )
    {
        return a > b ? a > c ? a : c : b > c ? b : c;
    }

Open in new window


0
for_yanCommented:
Look at the code I posted and it is much more understandable
- indeed you split into two parts and (forget about one leements first)
and apply the same function to left part, to right part and check for the common elment ioincrease
whchever one becmes gretetr that will be the maximum

and you split this way all the time until one of your parts becomes one element and then the function upon this one element will be this element itself and then
like in all recursions you actually go back through bigger elements
 
0
shampouyaAuthor Commented:
It doesn't matter if it's correct, it's a variation of what I see in my textbook, I just want to know how many times the recursion into the maxSumRec() method occurs. In line 15 and 16, two sets of 4 array elements are sent into the maxSumRec() method again, and then because of recursion, four sets of 2 array elements are sent into the following round, and finally, eight sets of 1 array element is sent into the maxSumRec() method before recursion stops due to the base case. Do you understand what I'm trying to ask here?
0
for_yanCommented:
No, it matters - you don't have maxiimum of three values at the bottom and it becomes not understandable at all
0
shampouyaAuthor Commented:
Sorry I just realized there was an error when I pasted my code. This is the correct code. Does it work for you when you run it?
public class test {

    public static void main(String[] args) {
        int[] myArray = {4,-2,5,-2,-1,-2};
        System.out.println(maxSumRec(myArray, 0, myArray.length -1));

    }

/**
     * Recursive maximum contiguous subsequence sum algorithm.
     * Finds maximum sum in subarray spanning a[left..right].
     * Does not attempt to maintain actual best sequence.
     */
    private static int maxSumRec( int [ ] a, int left, int right )
    {

        if( left == right )  // Base case
            return a[ left ] > 0 ? a[ left ] : 0;

        int center = ( left + right ) / 2;
        int maxLeftSum  = maxSumRec( a, left, center );
        int maxRightSum = maxSumRec( a, center + 1, right );


        int maxLeftBorderSum = 0, leftBorderSum = 0;
        for( int i = center; i >= left; i-- )
        {
            leftBorderSum += a[ i ];
            if( leftBorderSum > maxLeftBorderSum )
                maxLeftBorderSum = leftBorderSum;
        }

        int maxRightBorderSum = 0, rightBorderSum = 0;
        for( int i = center + 1; i <= right; i++ )
        {
            rightBorderSum += a[ i ];
            if( rightBorderSum > maxRightBorderSum )
                maxRightBorderSum = rightBorderSum;
        }

        return maxLeftBorderSum + maxRightBorderSum;
    }

}

Open in new window

0
for_yanCommented:
Yes it does - it works for me and gives the same result 11, but that was because of this particular
sequence - I'm sure you can invent the sequrnce when that code would have been be wrong.

And yes, you are right - the stopping point of recusrsion is when you get to one element, as this has obvious solution for maxRecSum() function
but you never compare eight sets of 1, you get to these ones, and from them
go backwards determining maxSumRec for bigger and bigger chunks
In fact you enter this method as a whole 15 times, but I could not have counted it  without computer
0
for_yanCommented:
And the code you pasted in ID:36907822
is still incorrect - in fact it does not use the values of
maxLeftSum and maxRightSum (only assigns to them and never uses them) which is wrong

the last return line should be

 return max3(maxLeftBorderSum + maxRightBorderSum, maxLeftSum,  maxRightSum );

and max3 is a simple function finding the biggest of three numbers

with this, the whole algorithm becomes much more understandable
 



0
for_yanCommented:
That's how any recursion works - you reprresent the function on bigger set
as made up of the functions on smaller sets and theese smaller sets  on even smaller sets until
you finally come to such small arguments when the function is obvious and then
you go back recalculatiing functions on bigger chunks from those form smaller chunks
and eventually come back to your original set
0
shampouyaAuthor Commented:
Oh ok, so I basically coded my program without even using maxLeftSum and maxRightSum, and all the  the recursive parts were entirely in those two variables, is that correct?

In my most recent example with the array {4,-2, 5,-2,-1,-2}, what is value of maxLeftSum and maxRightSum at the end of the program?
0
for_yanCommented:
>Oh ok, so I basically coded my program without even using maxLeftSum and maxRightSum, and all the  the recursive parts were entirely in those two variables, is that correct?

Absolutely correct.
I was sitting and trying to make any sense of it, until it occurred to me to browse internet and I found there this difference.
The main point of recursion is reduction of function on bigger argument to function(s) on smaller arguments - and tht's waht we see in this formula:
 return max3(maxLeftBorderSum + maxRightBorderSum, maxLeftSum,  maxRightSum );


>In my most recent example with the array {4,-2, 5,-2,-1,-2}, what is value of maxLeftSum and maxRightSum at the end of the program?
On the last stage for that array say we'll split into
4,-2,5 and -2,-1,-2

 maxLeftBorderSum = 5
maxRightBorderSum = 0
so maxLeftBorderSum + maxRightBorderSum  = 5

maxLeftSum will be 7
maxRightSum will be 0

so max3(maxLeftBorderSum + maxRightBorderSum, maxLeftSum,  maxRightSum ) = 7










0
shampouyaAuthor Commented:
How did you figure out that maxLeftSum will be 7?
0
for_yanCommented:
On the left side we have just three numbers 4,-2, 5
so we may have

4  
-2
5
4,-2
-2,5
4,-2,5  

I just summed them up and got the last one the biggest

Computer will of course split it again in two - sya 4,-2 and 5 and in this case
it will find that the sum "across common element" - will be the biggest

0
shampouyaAuthor Commented:
Ok let's say we have {-1, 2, 4, 3, 1, -8}. Eventually a[left] is what defines maxLeftSum and maxRightSum?

        if( left == right )
            return a[ left ] > 0 ? a[ left ] : 0;

        int maxLeftSum  = maxSumRec( a, left, center );
        int maxRightSum = maxSumRec( a, center + 1, right );
0
for_yanCommented:
eventually say we raeched

-1,2,4

we split it

to

-1,2 and 4

so whan we calculate rightsum - we have base case return and 4

when left sum we split

-1  and  2

out of this we have 2

so now we are back

with

2 and 4
 
both have base case return

but across-center wins with 6

and then we compare with the left three




0
shampouyaAuthor Commented:
Let me try it on the left side of this new array {-1, 2, 4, 4, 1, 3, 1, -8} and tell me if I'm correct:

we're looking at  {-1, 2, 4, 4}
we split the left side to (-1, 2) and (4, 4)
we split those two into (-1) and (2) and (4) and (4)

Now those seven subsequences in bold all get processed in the for loops of lines 25 to 38 of my most recent code above, and then they all compete against each other, and the biggest result wins the privilege of defining maxLeftSum?
0
for_yanCommented:
maybe you can think of it this way, but it never compares 7 subsequences - it either goes to one - when one will be result
or compares three - left , right and across
so

we split

-1,2  and  4,4

then calculatiing on the left we split

-1 and 2 - result 2

on the right we split

4 and 4

across the center wins - 8

now we have

2 and 8

across the ccenter wins 10

so 10 is the result of the function on the left side






0
shampouyaAuthor Commented:
Ok, my last question is, when the program gets down to one element at a time, the (-1) and (2) and (4) and (4), do those single numbers get processed in the for loops of lines 25 to 38?

Or better put, how many times does the first half of the array (-1, 2, 4, 4) cause the for loops in the program to be used? I DO NOT want to know how many times the for loops iterate, I just want a list of subsequences that INTERACT with the for loops. Here's what I think it is. Are these three statements true?

{-1, 2, 4, 4} interacts with the for loops
(-1, 2) and (4, 4) interact with the for loops
 (-1) and (2) and (4) and (4) interact with the for loops as single numbers
0
for_yanCommented:

OK, let;s start from two numbers in array (4,4):

maxSumRec(our arrya is 4,4)

so we don't exit on the base case as we have still two numbers
but then we split and

we got to first call with just one number array  4 and we return from this first call 4 on the base case
then we go to the lft-side call part also with one number and we return opn the base case with 4
and then we go into your loops 25-38 with leftsum 4, and rightsum 4
and we determine that acrosssum - 8 will be bigger - so 8 will be the result
so in your words it will mean that if we start frfom (4,4) we just go through these lines only once




0
shampouyaAuthor Commented:
oh ok so something like (4,4) is the smallest subsequence that would be processed by the for loops, and the for loops would never process a single digit like (4) because that is handled by the base case on line 17 and 18. Correct?
0
for_yanCommented:
Yes, this is correct.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
shampouyaAuthor Commented:
thanks!
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.