# Recursion in Programming

## Introduction

Recursion in programming is a technique where a function calls itself directly or indirectly. This approach allows us to break down complex problems into smaller, more manageable chunks.

For an example,

```python
def recursion():
    return recursion()
```

<div data-node-type="callout">
<div data-node-type="callout-emoji">⏲</div>
<div data-node-type="callout-text">Wait, don't call this function yet.</div>
</div>

It is essential to note that, there must be a base case and a recursive case in a function. If the base case is not mentioned, the function will call itself continuously and the system's stack will be full.

> That's how StackOverflow was found. Wait, what? Oops, that's when Stack Overflow exception is raised.

---

## Stack

A stack is a special area of computer memory that stores information about a computer program's active subroutines or functions.

A new frame is added to the call stack each time a function is called. This frame contains the return address, local variables, parameters, and saved registers.

> Yes yes, the behavior is similar to stack that we read in data structures.

---

## Base Case and Recursive Case

* **Base case:** A condition under which the function should stop calling itself, to prevent the infinite recursion.
    
* **Recursive Case:** The part of a function where it calls itself with a modified argument towards the base case.
    

Let's take an example,

```python
def print_upto_one(number):
    print(number)
    
    if number == 1:
        return
    
    print_upto_one(number-1)
```

Here, the function `print_upto_one` prints the passed `number`, calls itself again with decreased value. Also note that there is a condition to stop calling itself, i.e., when the value of `number` is **1**.

* `if number == 1: return` is a base case where the function will stop calling itself.
    
* `print_upto_one(number-1)` is a recursive case when the function calls itself with a decreased value.
    

---

## Recursion vs Infinite Loop

> Wait, this sounds a lot like infinite loop. What's the difference?

Not exactly. Let's understand it this way,

**Recursion** is like Russian nesting dolls where each doll contains a smaller doll inside until you reach the smallest one.

**Infinite Loop** is like a song stuck on repeat, playing the same part endlessly.

A new stack frame will be allocated to each function call in recursion whereas an infinite loop runs in the same amount of memory. That's why endless recursion will raise stack overflow error but infinite loop will keep running until the user or the system terminates it explicitly.

---

## Detailed Working of Recursion

Recursion works in stack memory. Each function called inside the function returns the value from where it is called.

Meaning, let's assume we have a function `A` and each function call as `A1`, `A2`, `A3` and so on.

Now, when `A1` calls `A2` and `A2` calls `A3`, `A3` will return value to `A2` and `A2` will return value to `A1` that the caller function can process.

Let's understand this with an example. This function calculates the sum of n natural numbers.

```python
def sum(n):
    if n == 1:
        return 1
    inner_func_value = sum(n - 1)
    return n + inner_func_value
```

**Visual Representation**

| Step | Function in Stack | Next Value (👇) | Return Value (👆) |
| --- | --- | --- | --- |
| 1 | sum(3) | 3 + sum(2) | 3 + 3 = 6 |
| 2 | sum(2) | 2 + sum(1) | 2 + 1 = 3 |
| 3 | sum(1) | 1 | 1 |

Here, the function calls itself with a decreased value until the passed value reaches to **1**. Then, every function output value is returned to the outer function, and so on.

> I know I know, this is a bit confusing while getting started.

---

## Factorial of a number using Recursion

Let's understand Recursion with one more example. This function will calculate the factorial of a number.

```python
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)
```

Now, let's also understand the function calls step by step.

```plaintext
factorial(3)                        # 1st call with value 3
    3 * factorial(2)                # 2nd call with value 2 (3-1)
        3 * (2 * factorial(1))      # 3rd call with value 1 (2-1)
        3 * (2 * 1)                 # 3rd call returns 1 (base case)
    3 * 2                           # 2nd call returns 2 (2 * 1)
6                                   # 1st call returns 6 (3 * 2)
```

Let's break down each step:

1. **First call**: `factorial(3)`
    
    * Calculates 3 \* factorial(2)
        
2. **Second call**: `factorial(2)`
    
    * Calculates 2 \* factorial(1)
        
3. **Third call**: `factorial(1)`
    
    * Base case: Returns 1 since factorial(1) = 1
        
4. **Return to second call**:
    
    * Calculates 2 \* 1 = 2
        
    * Returns 2
        
5. **Return to first call**:
    
    * Calculates 3 \* 2 = 6
        
    * Returns 6
        

So, the factorial of 3 is correctly calculated as 6.

---