aspose file tools*
The moose likes Beginning Java and the fly likes recursion situation baffles me Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "recursion situation baffles me" Watch "recursion situation baffles me" New topic
Author

recursion situation baffles me

Vonique Leary
Ranch Hand

Joined: Mar 24, 2008
Posts: 107
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
Sheriff

Joined: Aug 31, 2004
Posts: 11343

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


"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
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11479
    
  16

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

Joined: Dec 06, 2005
Posts: 1321

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.


Saifuddin..
[Blog][Linkedin] How To Ask Questions On JavaRanch My OpenSource
Vonique Leary
Ranch Hand

Joined: Mar 24, 2008
Posts: 107
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
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11479
    
  16

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.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11479
    
  16

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...
Shivit Agarwal
Ranch Hand

Joined: Feb 28, 2008
Posts: 82
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
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
Sheriff

Joined: Aug 31, 2004
Posts: 11343

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.
marc weber
Sheriff

Joined: Aug 31, 2004
Posts: 11343

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

Joined: Dec 06, 2005
Posts: 1321

Thanks for the nice thread, I must say.
marc weber
Sheriff

Joined: Aug 31, 2004
Posts: 11343

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
@Marc Weber

That was a cool way of replying. Great Job.
Vonique Leary
Ranch Hand

Joined: Mar 24, 2008
Posts: 107
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
 
Don't get me started about those stupid light bulbs.
 
subject: recursion situation baffles me