JAVA: Can someone explain this recursive code to me?

Question

I have some practice questions for Java here. We are supposed to determine the answer without using a compiler.

Refer to the following method:

public static int  product(int n){
if (n <= 1)
    return 1;
else 
    return n * product(n-2);
}

What is the output when product(6) is called?

A) 1

B) 8

C) 12

D) 48

E) 70

According to the answers, the correct output is 48. I don't really understand why this is true. 6 doesn't meet the base case, so it goes to the else statement. So 6, then product(6-2) = product(4), which goes to product(2), which goes to product(0) so that produces 6 * 4, 4 * 2, 2 * 0, 0 * 0. But that's 32, not 48? Is there something I'm missing?

product(25) returns -1181211311 for some reason, and I'm not really sure why this happens either. Is it because there's a stack overflow in the recursive calls or something?

Explanations would be extremely helpful, thank you!

`product(6) = 6 * product(4) = 6 * (4 * product(2)) = 6 * (4 * (2 * product(0)))` and `product(0)` is 1, then: 6 * 4 * 2 * 1 is actually 48. — Martín Schonaker, Apr 16 '14 at 02:41

score 6 · Accepted Answer · edited May 23 '17 at 12:04

6

I just answered the same thing in javascript here: Need help understanding recursive function example from Eloquent Javascript

Basically it's a stack, but it's easier to think of it as a math equation:

n = 6 * product(4)

n = 6 * 4 * product(2)

n= 6 * 4 * 2 * product(0)

n = 6 * 4 * 2 * 1

n = 48

25 throws a huge negative number because it's bigger than the max value of int..

edited May 23 '17 at 12:04

Community

1
1

answered Apr 16 '14 at 02:41

XeroxDucati

5,130
2
37
66

score 3 · Answer 2 · answered Apr 16 '14 at 02:41

3

The code works like this:

Round 1 : n = 6 so expression to be evaluated is 6 * product(4).
Round 2 : n = 4 so expression to be evaluated is 6 * 4 * product(2).
Round 3 : n = 2 so expression to be evaluated is 6 * 4 * 2 * product(0).

Since 0 < 1, the base case is reached, so product(0) = 1. Hence, the final expression is 6*4*2*1 which equals 48.

If you do this for 25, the value will overflow capacity of int, so you should change to long.

answered Apr 16 '14 at 02:41

shree.pat18

21,449
3
43
63

long won't fit the answer either – Amaury Medeiros Apr 16 '14 at 02:53
1

As per Oracle documentation, max value for `long` is 2^63 - 1 which evaluates to 9223372036854775807. Why shouldn't it fit then? I haven't tested it so I could be wrong of course :) – shree.pat18 Apr 16 '14 at 03:04
Sorry, you're absolutely right. I expressed myself poorly. I meant that using long won't solve the problem, because if you have product(50), for instance, it wouldn't fit a long :) – Amaury Medeiros Apr 16 '14 at 03:07
@AmauryMedeiros Actually 50 works too, but I appreciate the point you are trying to make. – shree.pat18 Apr 16 '14 at 03:08
for me, 50 returns 520469842636666622693081088000000. Am I doing something wrong? – Amaury Medeiros Apr 16 '14 at 03:13
@AmauryMedeiros My bad. 50 will overflow. – shree.pat18 Apr 16 '14 at 03:19

score 2 · Answer 3 · answered Apr 16 '14 at 02:41

2

Your code just multiplies the numbers from n to 1, decrementing by 2.

product(25) is supposed to return 7905853580625. Since it doesn't fit an int, your method will cause overflow.

answered Apr 16 '14 at 02:41

Amaury Medeiros

2,093
4
26
42

score 1 · Answer 4 · edited May 23 '17 at 12:04

Firstly, product(0) returns 1 because it meets the condition of <= 1, so the chain looks like this:

6 * product(4), 4 * product(2), 2 * product(0), 1 => 6 * 8, 4 * 2, 2 * 1

so, 6 * 8 = 48

Second,

product(25) is an integer overflow. The maximum value you can store in an int is 2,147,483,647 (explanation here: max value of integer), and your product() function, as written, would produce 7,905,853,580,625, much larger than that max value.

score 1 · Answer 5 · answered Apr 16 '14 at 03:12

As far as i can see answer is right. You are missing the main point that 2 will never be multiplied by 0. After product(2), 1 will be returned. When a method calls itself, new local variables and parameters are stored on the stack and method code will execute with these new variables from the start.

when product(6) is called

1.return 6*product(6-2)

product(4)

2.return 4*product(4-2)

product(2)

3.return 2*product(2-2)

product(0)

4.Which satisfies the if condition so 1 is returned

Hence, 6*4*2=48

JAVA: Can someone explain this recursive code to me?

5 Answers5