wood burning stoves 2.0*
The moose likes Beginning Java and the fly likes Recursion Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Recursion" Watch "Recursion" New topic
Author

Recursion

Nitin Kulkarni
Greenhorn

Joined: Aug 13, 2004
Posts: 7
My question relates to the following code which uses recursion.

1 public class factorial1
2 {
3public static void main(String[] args)
4{
5 System.out.println( "factorial of 4 is " + factorial(3));
6 }
7static int factorial( int n )
8 {
9 if ( n == 0 )
10 return 1;
11 else
12 return n * factorial( n-1 );
13}
14 }

prints--> factorial of 4 is 24

My question is how do you trace the execution of the program?

When the return statement is reached on line 12 the method factorial is called again. What is the
value of n * factorial( n-1 ) and where is it stored?
Tom Henner
Greenhorn

Joined: Jul 04, 2005
Posts: 18
You could put a debugging aide like
System.out.println( Integer.toString( factorial( n - 1 );
at the point you want to see the value. Since this is a method, I believe the values would be stored in the stack, with each recursion calling the next one till n == 1.
Kudret Serin
Ranch Hand

Joined: Aug 02, 2005
Posts: 167

You can perform Hoare Logic in order to reason about the correctness of your program.
Rick O'Shay
Ranch Hand

Joined: Sep 19, 2004
Posts: 531
That's an excellent question and the answer lies in how high level languages are realized in a typical computer. When a program is loaded in to memory it gets allocated an area of memory called a stack. When you call a method, the arguments are pushed on to the stack. Local variables are also pushed on the stack. When you return from the method, the local variables and the original method arguments are popped off the stack.

When you make a recursive call, a new set of arguments and local variables are pushed on to the stack. Provided you do not run out of stack space (2M per thread is the Java default) you can recurse indefinitely. Each method has it's own isolated frame of stack data so none of the preceding calls interfere with results in the current call.

Almost all modern languages and computers behave in precisely the same way with respect to passing arguments and creating local variables on the stack.
[ August 24, 2005: Message edited by: Rick O'Shay ]
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11161
    
  16

another way to think of it is each method is a piece of paper. you write on each piece all your current variable values. each time you call a new function, you put a new piece on top of all the others. (This is not a perfect analogy, as some variables can be seen across methods... perhaps there are holes in the paper...).

anyway, what happens in your code is something like this.

you call factorial with a value of (say) 5.

in your method, since n !=0, you go to line 12. here you are going to return the value you get by doing (5 * factorial(5-1)). I can't finish this until i make that method call of the "factorial(5-1)".

well, to calculate this, we need to call factorial(4). we'll write down that first 5, and hi-light the "factorial(4)" so that when we come back to this page, we stick our answer in here.

New piece of paper goes down. our n = 4. we get to line 12, and we want to return the value of (4 * factorial (4-1)). we'll write down that first 4, and hi-light the "factorial(3)" so that when we come back to this page, we stick our answer in here.


New piece of paper goes down. our n = 3. we get to line 12, and we want to return the value of (3 * factorial (3-1)). we'll write down that first 3, and hi-light the "factorial(2)" so that when we come back to this page, we stick our answer in here.
...

we now have a bunch of peices of paper in a "stack". we go into the routine with n = 0. we return 1. take that top peice of paper and throw it away. stick the 1 in the hi-lighted spot. i now need to return (1*1).

throw that peice of paper away. stick in the 1. i now need to return 2*1.

throw that peice of paper away. stick in the 2. i now need to return 3*2.

throw that peice of paper away. stick in the 6. i now need to return 4*6.
...
eventually i get to the last piece with the 5 * factorial(5-1). i get 120.

i would then throw that peice away, and return the 120 to the paper with the main() method (in this example).


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Nitin Kulkarni
Greenhorn

Joined: Aug 13, 2004
Posts: 7
Thanks for all your responses.
But can someone tell me how the logic of the following program goes line by line. It seems confusing. I have dispalyed the output and put in System.out.println statements to try to understand which line executes next.



prints

inside factorial method n is 3
inside else n is 3
inside factorial method n is 2
inside else n is 2
inside factorial method n is 1
inside else n is 1
inside factorial method n is 0
inside if n is 0
calling Integer.toString n is 1
inside factorial method n is 0
inside if n is 0
calling Integer.toString n is 2
inside factorial method n is 1
inside else n is 1
inside factorial method n is 0
inside if n is 0
calling Integer.toString n is 1
inside factorial method n is 0
inside if n is 0
calling Integer.toString n is 6
inside factorial method n is 2
inside else n is 2
inside factorial method n is 1
inside else n is 1
inside factorial method n is 0
inside if n is 0
calling Integer.toString n is 1
inside factorial method n is 0
inside if n is 0
calling Integer.toString n is 2
inside factorial method n is 1
inside else n is 1
inside factorial method n is 0
inside if n is 0
calling Integer.toString n is 1
inside factorial method n is 0
inside if n is 0
factorial of 3 is 6
Rick O'Shay
Ranch Hand

Joined: Sep 19, 2004
Posts: 531
The print statments might obscure the intent of the program and introduce error. In fact there is an error in your code so let's start with something simple.



Here is how to evaluate this. Trust me, it's easy:

As long as n is greater than zero, nothing interesting happens. The factorial method calls itself with n - 1 and waits for the return. If n is 100 there will be 99 recursive calls, and each call is going to wait on the next. Ponder that for a minute. If you come in with 13, you're going nowhere but back in to a factorial method call with the value 12. Nothing else happens, just a bunch of calls stacking up one behind the other.

Now here's the interesting part. When you get to zero recursion stops and you head back out, one call at a time. That's when the computations start kicking in.

Think of it in two steps: recursive calls stack up one behind the other, when recursion stops, the function returns one call at a time and each return value is used, however the caller wants. In this case to multiple n by the input value.

The first computation is associated with the last call: 1 * 1, then 2 * 1, then 3 * 2, then 4 * 6 ... finally 8 * 5040 where 8 is the very first call and 5040 is the result of all the recursive calls below it.

(I thought that was a little fuzzy so I cleaned it up).
[ August 27, 2005: Message edited by: Rick O'Shay ]
Barry Gaunt
Ranch Hand

Joined: Aug 03, 2002
Posts: 7729
This is the error line I believe Rick is referring to:

You are upsetting/confusing the your tracing by calling factorial here, because it is going to produce its own output trace.


Ask a Meaningful Question and HowToAskQuestionsOnJavaRanch
Getting someone to think and try something out is much more useful than just telling them the answer.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Recursion
 
Similar Threads
recursion situation baffles me
Qa dd'rouy Again
help in solving recursive problems??
how to soloving this problem?
Introduction and a question about recursion