aspose file tools*
The moose likes Beginning Java and the fly likes multiple recursion and stacks Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "multiple recursion and stacks" Watch "multiple recursion and stacks" New topic
Author

multiple recursion and stacks

B Iyer
Greenhorn

Joined: Oct 13, 2009
Posts: 4
Hi,

I have a question on recursion. It goes this way:

Suppose that we’re running a recursive algorithm where n is initially 16. Suppose that the
base case is n == 1. At each recursive step, two recursive method invocations are made with n/2.

a. How many total method invocations are needed (including the initial invocation)?
b. What are the most activation records that are on the stack at any one time during the
process?

I wrote a small piece of code. Is my code correctly portraying the question? If not, could some one please correct it? Could you please explain to me how the stack works. I have executed this program multiple times, but I don't understand the stack. I am now wondering if I have got the code right in the first place. Please help. Any input would be appreciated. Thanks very much

import java.io.*;
import java.lang.*;

public class printhalf
{
public static void main(String args[])
{
int i = 16;
printit(i);

}


public static void printit(int n)
{
if (n == 1)
return;
else
{
printit(n/2);
printit(n/2);

}
}

}

Thanks again,
biyer.
Vijitha Kumara
Bartender

Joined: Mar 24, 2008
Posts: 3775

B Iyer wrote:.. but I don't understand the stack.

Each time the method "printit" called it is executed in a different call stack (with own copy of local variable(s)). It's like executing another method.

SCJP 5 | SCWCD 5
[How to ask questions] [Twitter]
B Iyer
Greenhorn

Joined: Oct 13, 2009
Posts: 4
Hello Vijitha,

Thanks for the reply. When I execute the piece of code in debug mode(presuming I have understood the question right and have the code right), what happens is that first it goes through the 1st printin method recursively, I can see the values of i decrement 16,8,4,2,1. So n == 1 is true, it executes return and hits the next printin method. But this time when printin executes n is 2. 2/2 is 1 so n ==1, so it hits return, but the stack is still there, so the 1st printin get called again and then it gets confusing. Does my code meet the requirements of the question?

Might sound very trivial, but I have been trying to figure it out for almost a day before I put my post..

Please help,

Thanks,
Bhanu.
Hunter McMillen
Ranch Hand

Joined: Mar 13, 2009
Posts: 492

Hi Bhanu,

I have added some print statements to your code:


Go through your program with a debugging tool and see if you see any problems.
Also Im not really sure why you are using the return keyword in a void method.

-Hunter


"If the facts don't fit the theory, get new facts" --Albert Einstein
B Iyer
Greenhorn

Joined: Oct 13, 2009
Posts: 4
Hi Hunter,

Thanks for the reply. I do see what might probably be happening in the stack. How do I exit from a base case in a void method. I have a return without any value. It compiled fine. But is there a better way to do it?

Thanks,
bhanu.
Embla Tingeling
Ranch Hand

Joined: Oct 22, 2009
Posts: 237
B Iyer wrote:
I have a question on recursion. It goes this way:

Suppose that we’re running a recursive algorithm where n is initially 16. Suppose that the
base case is n == 1. At each recursive step, two recursive method invocations are made with n/2.

a. How many total method invocations are needed (including the initial invocation)?
b. What are the most activation records that are on the stack at any one time during the
process?


Each time printit is called an activation record is put on the stack. Each time printit is called recursively the recursive depth increases. The recursive depth decreases again when the recursion winds back after the stop criterion is met.

Now imagine that you only had ONE printit invokation with n/2 in each recursive step. Then n would be halved in successive recursive invokations like this,

1: n =16
2: n = 16/2 = 8
3: n = 8/2 = 4
4: n = 4/2 = 2
5: n = 2/2 = 1 // recursion stopped and starts winding back

So you have a recursive depth of 5 which is also the maximum number of activation records on the stack.

Now what happens if you put in another recursive call of printit so there are two?

Well, when the recursion is stopped and starts winding back in step 5 it returns to step 4 but there's another printit call waiting so there's a a second call waiting to be performed. The recursion once again increases to step 5 where the second call is stopped and starts winding back to step 4. This time there's no more printit call so it continues winding back to step 3 where there another printit call in the waiting ....... etcetera.

So in summary, the number of activation records on the stack never increases over the recursive depth. When there's one recursive printit call the call pattern is like the traversal of an imaginary linked list. When there are two recursive printit calls the call pattern instead is like the traversal of an imaginary binary tree. So the number of nodes in a linked list of length 5 and in a binary tree of depth 5 will give the number of recursive calls made in each case.
Vijitha Kumara
Bartender

Joined: Mar 24, 2008
Posts: 3775

B Iyer wrote:How do I exit from a base case in a void method. I have a return without any value.

By using return with no value is the way when we need to terminate a method in some point inside the method without throwing a RuntimeException which also ends the method.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 36478
    
  16
The if (n == 1) return; statement is probably unnecessary; leave that out and put if (n > 1) { . . . } round the remainder of the method.
B Iyer
Greenhorn

Joined: Oct 13, 2009
Posts: 4
Hi Embla, Vijitha and Ritchie,

Thank you very much for your reply and explanation. It is starting to make sense now.

Regards,
Biyer.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 36478
    
  16
You're welcome
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: multiple recursion and stacks
 
Similar Threads
Recursion
Recursion
Recursion Reciprocals
Question about mem allocation for recursive functions
Timing Methods