# Recursion

Nitin Kulkarni

Greenhorn

Posts: 7

posted 11 years ago

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?

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

Posts: 18

Rick O'Shay

Ranch Hand

Posts: 531

posted 11 years ago

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 ]

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 ]

posted 10 years ago

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).

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

Posts: 7

posted 10 years ago

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

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

Posts: 531

posted 10 years ago

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 ]

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

Posts: 7729

posted 10 years ago

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.

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.

It is sorta covered in the JavaRanch Style Guide. |