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??

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.

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.

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

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

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.

Have the determination of mirror which never fails to reflect in spite of being broken into pieces.<br /> <br />Kiss the hands you cannot bite.<br /> <br />An Optimist is one who starts taking a bath when he accidentally falls into the water.

Vonique Leary
Ranch Hand

Joined: Mar 24, 2008
Posts: 107

posted

0

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!

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

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
Ranch Hand

Joined: Feb 28, 2008
Posts: 82

posted

0

@Marc Weber

That was a cool way of replying. Great Job.

Vonique Leary
Ranch Hand

Joined: Mar 24, 2008
Posts: 107

posted

0

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!!!