recursion situation baffles me

[Vonique Leary]

Hello. Following is an example of recursion to compute a factorial of a number:

Code:
--------------------------------------------------------------------------------

class Factorial
int factR(int n) {
int result;if(n==1) return 1;
result = factR(n-1)* n;
return result;
}

class Recursion
public static void main(String arg[]) {
Factorial f = new Factorial();
System.out.println("Factorial of 5 is " + f.factR(5));
}
--------------------------------------------------------------------------------


The factorial of 5 works out to 120, but in looking at the above code (which I got out of Herbert Schildt's Java Beginner's book)I can't figure out how the result winds up being 120. It looks like factR(n-1) * n would always return the number minus 1 multiplied by itself, and not the result multiplied by the next number minus 1.

Can anyone explain where in the code the result of the previous computation gets multiplied by the next number minus 1??

Thanks, Vonique

[marc weber]

Suppose n is 5. Then...

result = fact(4) * 5

...where fact(4) is...

fact(3) * 4

...where fact(3) is...

fact(2) * 3

...where fact(2) is...

fact(1) * 2

...where fact(1) is 1.

So result is ((((1*2) * 3) * 4) * 5).

[fred rosenberger]

It looks like factR(n-1) * n would always return the number minus 1 multiplied by itself

Look carefully.

it doesn't return (n-1) * n, but instead returns (factR(n-1)) * n

that "factR(n-1)" is a method call, like any other method call. it just happens that the method is calling itself - that's what recursion is.

[Muhammad Saifuddin]

well described marc,

hi Vonique,

little changes will make your code more effective.

change this code

if(n==1)
    return 1;

with this.

if(n<=1)
   return n;

now try your solution with 0(zero) value and then try with little change.

[Vonique Leary]

Marc,

so 5x4 = 20, 4x3= 12, 3x2 = 6, and 2x1 = 2. Which is the part of the code that makes 5x4x3x2 = 120???

I must be missing something about the fact that the method is calling itself. When the method calls itself, is it somehow retaining the previous value of the multiplication and in the end comes out with 120?

I just don't get it. Can you see where I'm going wrong?

Thanks for trying to help, though. I appreciate it. Thanks to everyone else who responded too.

Von

[fred rosenberger]

think of it like this... when n = 5...

 result = factR(n-1)* n; 

as SOON as you hit that "factR(n-1)", that line of code is "suspended", as it were. we STOP executing it, and go into the new method.

in the new method, we have n=4. we get to factR(n-1), and again, STOP executing that line, while we make a new method call... and so on. eventually, we get down to n=1, and we can simply return '1'.

it's like a stack of papers. at first, you have nothing in your stack. you then say "I'm gonna figure out what 5! is. I know 5! is equal to 5 times 4!. i'll write that down". You know you need to set that aside until you figure out what 4! is. you get a new piece of paper, and write down on it 4! = 4 * 3!. again, you can't go any further here until you figure out 3!, so you set that piece on top of the first one. on a NEW piece, you write 3! = 3 * 2!. again, you set THAT one on top of all the others, and then another with 2! = 2 * 1!.

you grab your last piece of paper, and write 1! = 1. cool. you can now remember 1, and look at the top paper that says 2! = 2 * 1!. you can substitute 1 in for 1!, giving you 2! = 2 * 1 = 2. you throw that one away, remembering the value 2.

the next piece says "3! = 3 * 2!" which becomes 3*2, or 6. throw it away.

4! = 4 * 3!, or 4 * 6, or 24.

throw away, next piece says 5 * 4!, or 5 * 24, or 120.

[fred rosenberger]

or, look at it this way. what if we had a bunch of methods...

int oneFact() { 
  return 1;
}
 
int twoFact() { 
  return 2 * oneFact();
}
 
int threeFact() {
  return 3 * twoFact();
}
 
int fourFact() {
  return 4 * threeFact();
}
 
int fiveFact() {
   return 5 * fourFact();
}

now, call fiveFact(); you can see that's going to return:
5 * (fourFact())
but you can substitute in what fourFact() does...
5 * (4 * threeFact());
which becomes
5 * (4 * (3 * twoFact())); becomes
5 * (4 * (3 * (2 * oneFact()))); becomes
5 * (4 * (3 * (2 * (1))));

hopefully you can see in the pattern of all those methods that all we're doing is to calculate it is multiplying a value x by (x-1)! so rather than spelling out all 5 methods, you write it with a variable...

[Shivit Agarwal]

Don't worry . In the beginning most of the programmer face the same problem withe recursion.

I too had the same problem when I started Recusrion in C. But once you understands, how it work you will be in love with it.

[Vonique Leary]

Okay, I think I get it now (I think). Tell me if my thinking is going in the right direction. So, rather than computing the value of n-1*n each go around, it is just saying that the method will call the method using n-1 each time until it gets to 1. Then it will compute the value of the whole thing, which would be like calling each method individually and then multiplying them together at the end to get 120 (using 5, as in the example).

Am I going in the right direction with this? It's what I think you are saying anyway.

I'm probably going to have to let this sink in for a while and try other examples. In the meantime, thank you everyone for all the great explanations. I do think I'm starting to get the concept, but I will have to review each answer several times before I really have it down!

Have a great weekend!
Von

[marc weber]

Originally posted by fred rosenberger:
or, look at it this way. what if we had a bunch of methods...

int oneFact() { 
  return 1;
}
 
int twoFact() { 
  return 2 * oneFact();
}
 
int threeFact() {
  return 3 * twoFact();
}
 
int fourFact() {
  return 4 * threeFact();
}
 
int fiveFact() {
   return 5 * fourFact();
}

...

I'll admit it. I actually wrote something like that (down to about 10 levels!) before I understood recursion.

[marc weber]

Originally posted by Vonique Leary:
...So, rather than computing the value of n-1*n each go around, it is just saying that the method will call the method using n-1 each time until it gets to 1. Then it will compute the value of the whole thing...

Right!

It's not separate operations: 5x4 = 20, 4x3= 12, 3x2 = 6, and 2x1 = 2.

Instead, it's one deep calculation: ((((1*2) * 3) * 4) * 5).

[Muhammad Saifuddin]

Thanks for the nice thread, I must say.

[marc weber]

I think this is clear now, but let me try to frame this as an analogy.

You want to know what 5 factorial is, so you pick up the phone and call Amanda. "What's 5 factorial?"

Amanda realizes that before she returns an answer, she needs to know what 4 factorial is, so she says, "Let me put you on hold while I make another call." Amanda then calls Becky, "What's 4 factorial?"

Becky realizes that before she returns an answer, she needs to know what 3 factorial is, so she says, "Let me put you on hold while I make another call." Becky then calls Chrissie, "What's 3 factorial?"

Chrissie realizes that before she returns an answer, she needs to know what 2 factorial is, so she says, "Let me put you on hold while I make another call." Chrissie then calls Dessa, "What's 2 factorial?"

Dessa realizes that before she returns an answer, she needs to know what 1 factorial is, so she says, "Let me put you on hold while I make another call." Dessa then calls Ethel, "What's 1 factorial?"

Ethel says, "That's easy." So Ethel returns her answer to Dessa, "1 factorial is 1," and hangs up the phone.

Dessa now has the information she needs. She multiplies 1 * 2, returns her answer to Chrissie, "2 factorial is 2," and hangs up the phone.

Chrissie now has the information she needs. She multiplies 2 * 3, returns her answer to Becky, "3 factorial is 6," and hangs up the phone.

Becky now has the information she needs. She multiplies 6 * 4, returns her answer to Amanda, "4 factorial is 24," and hangs up the phone.

Amanda now has the information she needs. She multiplies 24 * 5, returns her answer to you, "5 factorial is 120," and hangs up the phone.

This illustrates the pattern of method calls and returns. It is not call-return, call-return, call-return... Instead, it is call, call, call... (until some criteria is met), followed by return, return, return...

Of course, with recursion, Amanda, Becky, Chrissie, Dessa, and Ethel are different names for the same person. In order to return one result, the method calls itself, over and over as necessary.

(Note how important it is to eventually meet some criteria for not making another recursive call. In this case, that happens when the value passed is 1. Without this, there would would be infinite recursion: Call, call, call, call... Until the program eventually crashes.)
[ April 05, 2008: Message edited by: marc weber ]

[Shivit Agarwal]

@Marc Weber

That was a cool way of replying. Great Job.

[Vonique Leary]

Yes, that was a great explanation! It really helped to solidify my understanding of recursion, though I will have to play around with more examples, but you have given me a great start!

Thanks to everyone who responded. What a great forum. I have been looking for a place like this for a long time to ask questions. Now I know where to come with my Java questions!!!

Vonique