• Post Reply Bookmark Topic Watch Topic
  • New Topic

Making sense of recursion  RSS feed

 
Ranch Hand
Posts: 67
Android Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Firefox Browser IntelliJ IDE Java Linux Spring
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Brian Barrick wrote: . . . It's an example from the book . . .
Which book? And which page, please?
 
Paweł Baczyński
Bartender
Posts: 2087
44
Firefox Browser IntelliJ IDE Java Linux Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Also, your method throws StackOverflowError if n=0 when it should return 1 as 0! = 1.
 
Brian Barrick
Ranch Hand
Posts: 67
Android Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Firefox Browser IntelliJ IDE Java Linux Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Firefox Browser IntelliJ IDE Java Linux Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Brian Barrick wrote:I don't understand the 1L part.

1 is int literal.
1L is long literal.
 
Brian Barrick
Ranch Hand
Posts: 67
Android Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!