• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

multiple recursion and stacks

 
B Iyer
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 3916
9
Chrome Fedora Hibernate
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
B Iyer
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
B Iyer
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 237
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 3916
9
Chrome Fedora Hibernate
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 50168
79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 50168
79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're welcome
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic