Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

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

Posted on 2011-10-03
30
Medium Priority
?
472 Views
Last Modified: 2012-05-12
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

0
Comment
Question by:shampouya
  • 17
  • 13
30 Comments
 
LVL 47

Expert Comment

by:for_yan
ID: 36906405
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
 

Author Comment

by:shampouya
ID: 36906476
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
 
LVL 47

Expert Comment

by:for_yan
ID: 36906492
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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 

Author Comment

by:shampouya
ID: 36906615
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
 
LVL 47

Expert Comment

by:for_yan
ID: 36906746
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
 
LVL 47

Expert Comment

by:for_yan
ID: 36906753
when you call recusrive method twice in the body it really becomes difficult to understand
0
 

Author Comment

by:shampouya
ID: 36907544
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
 
LVL 47

Expert Comment

by:for_yan
ID: 36907737


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
 

Author Comment

by:shampouya
ID: 36907759
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
 
LVL 47

Expert Comment

by:for_yan
ID: 36907763

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
 
LVL 47

Expert Comment

by:for_yan
ID: 36907769
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
 

Author Comment

by:shampouya
ID: 36907776
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
 
LVL 47

Expert Comment

by:for_yan
ID: 36907780
No, it matters - you don't have maxiimum of three values at the bottom and it becomes not understandable at all
0
 

Author Comment

by:shampouya
ID: 36907822
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
 
LVL 47

Expert Comment

by:for_yan
ID: 36907840
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
 
LVL 47

Expert Comment

by:for_yan
ID: 36907848
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
 
LVL 47

Expert Comment

by:for_yan
ID: 36907858
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
 

Author Comment

by:shampouya
ID: 36907895
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
 
LVL 47

Expert Comment

by:for_yan
ID: 36907918
>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
 

Author Comment

by:shampouya
ID: 36907951
How did you figure out that maxLeftSum will be 7?
0
 
LVL 47

Expert Comment

by:for_yan
ID: 36907959
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
 

Author Comment

by:shampouya
ID: 36907987
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
 
LVL 47

Expert Comment

by:for_yan
ID: 36908001
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
 

Author Comment

by:shampouya
ID: 36908056
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
 
LVL 47

Expert Comment

by:for_yan
ID: 36908073
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
 

Author Comment

by:shampouya
ID: 36908121
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
 
LVL 47

Expert Comment

by:for_yan
ID: 36908172

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
 

Author Comment

by:shampouya
ID: 36908188
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
 
LVL 47

Accepted Solution

by:
for_yan earned 2000 total points
ID: 36908197
Yes, this is correct.
0
 

Author Closing Comment

by:shampouya
ID: 36908200
thanks!
0

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Java had always been an easily readable and understandable language.  Some relatively recent changes in the language seem to be changing this pretty fast, and anyone that had not seen any Java code for the last 5 years will possibly have issues undeā€¦
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Viewers will learn one way to get user input in Java. Introduce the Scanner object: Declare the variable that stores the user input: An example prompting the user for input: Methods you need to invoke in order to properly get  user input:
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.
Suggested Courses

580 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question