Recursion : Part - 01

What is Recursion

Recursion is a programming technique where a function calls itself in order to solve a problem.

The problem is broken down into smaller, more manageable sub-problems of the same type.

This process continues until the problem can be solved directly, which is known as the base case.

Once the base case is reached, the function stops calling itself and the results of the sub-problems are combined to produce the final solution.

Key Concepts of Recursion:
Base Case
Recursive Case
Stack Memory

Visualizing Recursion with Fibonacci Numbers

I have a function called fib(4). When I call it, it returns the value 3. Let’s break it down step by step.

Step 1: Draw the Recursion Tree

To understand the recursion, we can draw a recursion tree for the Fibonacci number. When the function runs, it calls the previous two values and continues this process until the base case is reached. According to the formula, we know that fib(n) = fib(n-1) + fib(n-2). Here is the tree:

Step 2: Reach the Base Case

Step 3: Return the Values from the Base to the Top

So far, we have a clear understanding of how the recursion tree works and how the values are returned. If we consider how a stack works, take a look at this:

It starts from the main call and follows the green line. When a call begins, it directly goes to the bottom, then the function executes from the bottom up.

code

java

public class Fibo{
    public static void main(String[] args){
         System.out.println(fibo(4));
    }

    static int fibo(int n){
        if(n <= 1){
            return n;
        }
        return fibo(n-1) + fibo(n-2);
    }
}

• Python

def fibo(n):
    if n <= 1:
        return n
    return fibo(n-1) + fibo(n-2)

if __name__ == "__main__":
    print(fibo(4))