Recursion snippet: Please explain how the below code works-CodePudding

Here's a code that prints 16, but I don't understand how it works. Can you please explain? My logic: if n = 2, returned value = 2*(2 1) = 6

def fun(n):
    if(n == 4):
        return n
    else:
        return 2*fun(n 1)


print(fun(2))

CodePudding user response：

It's a basic example of recursion, i.e., a function repeatedly calling itself. The function gets called with 2 as a parameter. The function realises that the parameter is not 4 and hence reaches the return 2*fun(n 1) line. So it's supposed to return 2 * fun(3), for which it calls itself with 3 as parameter. 3 is still not 4, so we get to return 2*fun(n 1) again and call it on 4. Now, on this function call, n == 4, so the third function call returns 4 to the second function call. That one returns 8 (24) to the first, and the first returns 16 (28). In other words, you're first building up a chain of recursive function calls which then wraps itself up in reverse order.

CodePudding user response：

if n=2 the returned value will be 2 * 2 * 4=16 since you are reaching this line twince

return 2*fun(n 1)

this is there "2*2" is coming from

and when n:=4 you return n so you return 4

if(n == 4):
    return n

this is where * 4 is coming from

in conclusion 2 * 2 * 4=16

hope I could help :)

CodePudding user response：

First, you passed 2 as an argument to the function fun(). As n or 2 is not equal to 4 (as per the if condition), we go to the else condition. So we get:

return 2 * fun(n   1)

which is

return 2 * fun(2   1)

So you called the same function again, this is recursion. Now again, 3 is passed as an argument to the function. 3 is not equal to 4, which takes us to the else condition and we call the function by

return 2 * fun(3   1)

fun(4) returns 4 itself. so we return to the above function and instead of

return 2 * fun(3   1)

we can replace it as

return 2 * 4 gives us 8, and the 8 returns to our first call. Here, we get 2 * 8 = 16.

I have tried my best to explain it. Recursion is a confusing topic. If you still need more clarity, Please go through this doc