CODEWITHSUNDEEP
recursion
user3450277
user3450277

Reputation: 436

JAVA: Can someone explain this recursive code to me?

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!

Upvotes: 1

Views: 702

Answers (5)

Hello World
Hello World

Reputation: 983

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

Upvotes: 1

sddamico
sddamico

Reputation: 2130

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.

Upvotes: 1

XeroxDucati
XeroxDucati

Reputation: 5200

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

Upvotes: 6

shree.pat18
shree.pat18

Reputation: 21757

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.

Upvotes: 3

Amaury Medeiros
Amaury Medeiros

Reputation: 2233

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.

Upvotes: 2

Related Questions