##
**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))
```

## Top comments (0)