Recursive method If we call the program f(3) [duplicate]

Question

I have this code and i know that the answer is 6 but i do not know how we reached to that answer.

i know that the steps of the program are as follows:

f(3)

2*f(4)

1+f(2)

1+f(1)

Also how do we tell the recursive method to stop?

public static int f(int n) {        
    if (n <= 1) return 1;           

    if (n % 2 == 0) return 1 + f(n / 2);  

    return 2 * f(n+1);

Expected outcome is 6.

"how do we tell the recursive method to stop?" By having a base case (n <= 1) where no recursive call is made. "i do not know how we reached to that answer" Run through each step of the algorithm with pen and paper (or by adding logs in the code and running it if you prefer that). — Michael
– Michael, Commented Apr 26, 2019 at 10:37
The method will stop once you eventually reach the basic step, which is if (n <= 1) return 1; . So Basically what is happening rn is that everytime you go in either the second "if" statement or the return, you call the same function again, and it will keep doing that until you eventually return 1. — vc73
– vc73, Commented Apr 26, 2019 at 10:38
This would be an appropriate time to pick up paper and a pencil :) — Soutzikevich
– Soutzikevich, Commented Apr 26, 2019 at 11:55

Syed Mehtab Hassan · Accepted Answer · 2019-04-26 10:48:11Z

0

    f(3)                     -> does not match any condition return 2* f(n+1)
    (2 * f( 4 ))             -> match the second condition  return  1 + f(n / 2)
    (2 * (1 + f(2)))         -> match the second condition  return  1 + f(n / 2)
    (2 * (1 + (1 + f(1))))   -> match the first condition  return  1 and method does not call it self so it stop
    (2 * (1 + (1 + 1)))      -> By bodmas rule = 6

answered Apr 26, 2019 at 10:48

Syed Mehtab Hassan

1,3571 gold badge12 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

ahemberg · Accepted Answer · 2019-04-26 11:02:51Z

This article on recursion explains it quite well: How recursion works

In your case a sequence of method calls is put on a call stack and then traversed just like you're saying. Everytime we call the function recursively that call is put on top of the call stack:

f(3) -> 2 * f(4)
f(4) -> 1 + f(2)
f(2) -> 1 + f(1)
f(1) -> 1

When this is computed we then get

f(1) = 1
f(2) = 1 + 1 = 2
f(4) = 1 + 2 = 3
f(3) = 2 * 3 = 6

And then we return the value of the last computation. So we don't tell the recursive method to stop, but rather we run the function recursively building up a stack of method calls until we reach a function call that is no longer recursive, in this case f(1). Once we have reached that point we compute the call stack until we reach the first call taking the result from the previous execution with us.

If the input to your method never ends up in a call to f(1) then the recursion will not stop and you will get stuck. Your method will not have that issue, but consider this method:

public static int bad(int i) {
    return bad(i + 1);
}

That method will never reach a terminating state and will fill up your call stack until you run out of memory. So it is important to make sure that your function does not cause infinite recursion. Many IDEs will warn you about this.

Collectives™ on Stack Overflow

Recursive method If we call the program f(3) [duplicate]

2 Answers 2

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Linked

Related