Understand the recursion without stack

Understand the recursion without stack

For get about the recursion for some time.

Just we recall how the basic function works.

def fun():
    return 'Malavi Pande'
output = fun()
print(output)

output : 
Malavi Pande

most of the people say to moving forward with recursion one need to understand how functions work. But all of them will fail/miss how we can make analogy of function with recursion.

So, first we will discuss how function works.

  1. Function only start executing whenever it is called

  2. Function got returned where is it called.

That's it as simple as it looks., This is the same thing happening under the hood in case of recursion as well. But no one will talk much about it. instead they directly just into stack execution.

Let's see with the analogy of mine how can we understand fabonacci series formation.

If we have 2 or more recursive function calls doing some operations we start executing from left to right

1 def fibo(n):
2    if n == 0 or n == 1:
3        return n
4    return fibo(n-1) + fibo(n-2)
5 result = fibo(3)
6 print(result)

output: 
2

Our first point

  1. First the code start executing at line number 5 because it is called there

Second point

  1. Function got returned at the same line number 5 because it got returned where it is called.

After calling the fibo function with parameter 3 function looks like below.

def fibo(3)
    if n == o or n == 1:
        return n 
    return fibo(2) + fibo(1)

In the last return statement we actually need to return something but we don't have anything to return instead we are calling the same function with argument 2 and 1

This is where people say until fibo(2) & fibo(1) return something fibo(3) will be in stack.

But instead we can also say this as it is a separate function call with argument 2 so, the code look like this

def fibo(2)
    if n == o or n == 1:
        return n 
    return fibo(1) + fibo(0)

In this case also the last return has same function calls with arguments as 1 and 0 so, As we know the flow is from left to right.

def fibo(1)
    if n == o or n == 1:
        return n

with argument 1 we hit the base condition so here there is no further recursive function calls & we actually return some value.

Thus, fibo(1) call returning value 1 but where it will return .. ? from where it is called. so, it got returned to fib(2)

def fibo(2)
    if n == o or n == 1:
        return n 
    return fibo(1) [ 1 will returned to here ] + fibo(0)

As we completed the first part of fibo(2) the compiler will move right to see what further it has to do.

As we have recursive call with argument 0 the code look like this.,

def fibo(0)
    if n == o or n == 1:
        return n

As this call return 0 as a value it got returned where is called so.,

def fibo(2)
    if n == o or n == 1:
        return n 
    return fibo(1) [ 1 will returned to here ] + fibo(0) [ 0 will returned to here

After this for the compiler to move right there is nothing to do so., for now fibo(2) has it's whole answer ready. But wait where it needs to return obviously where is it called consequently.,

def fibo(3)
    if n == o or n == 1:
        return n 
    return fibo(2) [1+0 will returned to here]  +  fibo(1)

For the fibo(3) the the one part is done but fibo(1) is left so, again there is a separate function call with argument 1

def fibo(1)
    if n == o or n == 1:
        return n

As we know it will return 1 and it got returned to where it is called so.,

def fibo(3)
    if n == o or n == 1:
        return n 
    return fibo(2) [1+0 will returned to here]  +  fibo(1) [ 1 will returned to here]

therefore as a whole fibo(3) is returning 2 according to the 2nd point it will returned where it is called hence.,

1 def fibo(n):
2    if n == 0 or n == 1:
3        return n
4    return fibo(n-1) + fibo(n-2)
5 result = fibo(3) [ 2 will returned to here ] 
6 print(result)

output: 
2

In simple this is flow of recursion without stack most of the people will make analogy of stack but I when I start understanding this in terms of normal function call principle life became so easy.

I would love to know which one you like the most.

Did you find this article valuable?

Support Malavi Pande by becoming a sponsor. Any amount is appreciated!