recursion situation baffles me

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

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

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

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

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.

well described marc,

hi Vonique,

little changes will make your code more effective.

change this code

with this.

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

hi Vonique,

little changes will make your code more effective.

change this code

with this.

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

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

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

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

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.

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

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.

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.

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

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.

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

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

Thanks for the nice thread, I must say.

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 ]

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

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

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

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

Ethel says, "That's easy." So Ethel

Dessa now has the information she needs. She multiplies 1 * 2,

Chrissie now has the information she needs. She multiplies 2 * 3,

Becky now has the information she needs. She multiplies 6 * 4,

Amanda now has the information she needs. She multiplies 24 * 5,

This illustrates the pattern of method calls and returns. It is

Of course, with

(Note how important it is to eventually meet some criteria for

[ April 05, 2008: Message edited by: marc weber ]

@Marc Weber

That was a cool way of replying. Great Job.

That was a cool way of replying. Great Job.

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

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

This thread has been viewed 1170 times.

All times above are in ranch (not your local) time.

The current ranch time is

Oct 17, 2018 08:47:59.

The current ranch time is

Oct 17, 2018 08:47:59.