programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Making sense of recursion

Ranch Hand
Posts: 67
In the following snippet I'm calling this method and passing it the value of 3. In trying to use the print statements to make sense of it all I think I've just confused it even further. The out put is:

3
2
2 2
3 6
Factorial of 3 is 6.

It all makes sense until the third line of output. Why would the variables n and result both = 2 at the same time after the recursion has occurred and before returning the result?

Marshal
Posts: 56610
172
What is wrong with the method? It looks correct. If you are using an int, don't pass an argument greater than 12 otherwise you will get an overflow error.

The problem is that you are printing the argument then recursing then printing the result. Change line 7 to read
System.out.printf("%d! = %d%n", n, result);
… because the bang sign is used to mean factorial.

Bartender
Posts: 689
17
The line you have is

So you're printing 'n' (which is 2), and factR(n-1) * n, which is 1*2, which is 2.

factR(1) is defined to be 1 earlier in the method.

Brian Barrick
Ranch Hand
Posts: 67
Campbell Ritchie wrote:What is wrong with the method? It looks correct. If you are using an int, don't pass an argument greater than 12 otherwise you will get an overflow error.

The problem is that you are printing the argument then recursing then printing the result. Change line 7 to read
System.out.printf("%d! = %d%n", n, result);
… because the bang sign is used to mean factorial.

Nothing is wrong with it, it works fine. It's an example from the book but the book doesn't explain it enough for me to grasp exactly what's going on. I just put the println statements in to see the values as the code ran. I was surprised to see it run the second print statement twice and showing those values then returning with the correct value. I understand what it's doing, I just don't understand the flow or how it's doing it.

Bartender
Posts: 2087
44
• 1
What happens is:
- factR(3) is called (when you call factR(3))
- n = 3
- 3 is printed (line 5)
- factR(2) is called (line 6)
- n = 2
- 2 is printed (line 5)
- factR(1) is called (line 6)
- n = 1
- 1 is returned (line 4)
- the result of factR(1) is multiplied by n=2 and assigned to variable result (line 6)
- result = 2
- 2 2 is printed (line 7)
- 2 is returned (line 8)
- the result of factR(2) is multiplied by n=3 and assigned to variable result (line 6)
- result = 6
- 3 6 is printed (line 7)
- 6 is returned (line 8)
- ... there goes whatever is after call to factR(3)

Campbell Ritchie
Marshal
Posts: 56610
172
Brian Barrick wrote: . . . It's an example from the book . . .
Which book? And which page, please?

Paweł Baczyński
Bartender
Posts: 2087
44
Also, your method throws StackOverflowError if n=0 when it should return 1 as 0! = 1.

Brian Barrick
Ranch Hand
Posts: 67
Paweł Baczyński wrote:What happens is:
- factR(3) is called (when you call factR(3))
- n = 3
- 3 is printed (line 5)
- factR(2) is called (line 6)
- n = 2
- 2 is printed (line 5)
- factR(1) is called (line 6)
- n = 1
- 1 is returned (line 4)
- the result of factR(1) is multiplied by n=2 and assigned to variable result (line 6)
- result = 2
- 2 2 is printed (line 7)
- 2 is returned (line 8)
- the result of factR(2) is multiplied by n=3 and assigned to variable result (line 6)
- result = 6
- 3 6 is printed (line 7)
- 6 is returned (line 8)
- ... there goes whatever is after call to factR(3)

Ooh...so the there are three returns taking place. I didn't consider that. I was assuming that when the final return was reached it would return flow back to the line calling this method.

The book discusses recursion as having a telescopic effect and this explanation makes sense now. Thank you.

Brian Barrick
Ranch Hand
Posts: 67
Campbell Ritchie wrote:
Brian Barrick wrote: . . . It's an example from the book . . .
Which book? And which page, please?

Java A Beginner's Guide 6th Edition by Herbert Schildt

Brian Barrick
Ranch Hand
Posts: 67
Paweł Baczyński wrote:Also, your method throws StackOverflowError if n=0 when it should return 1 as 0! = 1.

Here is the full program. It runs fine.

Brian Barrick
Ranch Hand
Posts: 67
Campbell Ritchie wrote:
Brian Barrick wrote: . . . It's an example from the book . . .
Which book? And which page, please?

I'm sorry, it's Page 204. This isn't a question from a book for exam purposes or anything. I'm self studying and simply asking the question on my own. The code, minus the added print statements, is strictly from the book.

Campbell Ritchie
Marshal
Posts: 56610
172
The way I would write that method isI think that works up to 21! before you get an overflow error.

Paweł Baczyński
Bartender
Posts: 2087
44
Brian Barrick wrote:Here is the full program. It runs fine.

It runs fine because you didn't call factR(0).

Brian Barrick
Ranch Hand
Posts: 67
Campbell Ritchie wrote:The way I would write that method isI think that works up to 21! before you get an overflow error.

I don't understand the 1L part.

Campbell Ritchie
Marshal
Posts: 56610
172
It means if i == 0 you use the bit betweeen the ? and the : viz 1L.
1L is 1 occupying 64 bits rather than the usual 32.
If i is not 0 then it means the part to the right of the : viz i multiplied by factorial of 1 less.

Paweł Baczyński
Bartender
Posts: 2087
44
Brian Barrick wrote:I don't understand the 1L part.

1 is int literal.
1L is long literal.

Brian Barrick
Ranch Hand
Posts: 67
Campbell Ritchie wrote:It means if i == 0 you use the bit betweeen the ? and the : viz 1L.
1L is 1 occupying 64 bits rather than the usual 32.
If i is not 0 then it means the part to the right of the : viz i multiplied by factorial of 1 less.

If(i == 0)
return = 1L;
else
i * factorial(i - 1);

Is that a correct translation?

Campbell Ritchie
Marshal
Posts: 56610
172
Yes.