# recursion situation baffles me

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

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

"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." *~Joe Strummer*

sscce.org

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.

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

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

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.

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

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

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

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.

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

Originally posted by fred rosenberger:

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

...

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

"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." *~Joe Strummer*

sscce.org

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

"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." *~Joe Strummer*

sscce.org

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 ]

*~Joe Strummer*

sscce.org

That was a cool way of replying. Great Job.

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.

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