Recursion

[Nitin Kulkarni]

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]

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]

You can perform Hoare Logic in order to reason about the correctness of your program.

[Rick O'Shay]

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]

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

[Nitin Kulkarni]

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.

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

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]

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.

public int factorial(int n) 
{
   return n == 0 ? 1 : n * factorial(n - 1);
}
 
void test() 
{ 
   System.out.print( factorial( 8 ) ); 
}

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]

This is the error line I believe Rick is referring to:

System.out.println("calling Integer.toString n is      " + Integer.toString(n*(factorial( n - 1 ))));  

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