# Recursion

Recursion is a programming technique where a function calls itself to solve a problem. It breaks down a complex problem into smaller, self-similar subproblems.

## 1. The Core Concept

A recursive function typically has two essential parts:

1.  **Base Case:** The condition that stops the recursion. Without this, the function would call itself infinitely (Infinite Recursion).
2.  **Recursive Step:** The part where the function calls itself with a modified argument, moving closer to the base case.

## 2. Example: Factorial

The factorial of a number $n$ (denoted as $n!$) is the product of all positive integers less than or equal to $n$.
*   $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$
*   Recursive definition: $n! = n \times (n-1)!$

```python
def factorial(n):
    # 1. Base Case
    if n == 1:
        return 1
    
    # 2. Recursive Step
    return n * factorial(n - 1)

print(factorial(5)) # Output: 120
```

## 3. How it Works (The Call Stack)

When a function calls itself, the computer adds a new frame to the **Call Stack**.

Execution of `factorial(3)`:
1.  `factorial(3)` calls `factorial(2)`. (Stack: `[fact(3)]`)
2.  `factorial(2)` calls `factorial(1)`. (Stack: `[fact(3), fact(2)]`)
3.  `factorial(1)` hits the base case and returns `1`. (Stack: `[fact(3), fact(2)]`)
4.  `factorial(2)` receives `1`, calculates `2 * 1 = 2`, and returns `2`. (Stack: `[fact(3)]`)
5.  `factorial(3)` receives `2`, calculates `3 * 2 = 6`, and returns `6`. (Stack: `[]`)

## 4. Stack Overflow

If you forget the base case, or if the recursion is too deep, the call stack fills up and runs out of memory. This causes a **Stack Overflow** error.

## 5. Recursion vs. Iteration

Any problem that can be solved recursively can also be solved iteratively (using loops).

*   **Recursion:** Often cleaner and more readable for problems involving trees, graphs, or mathematical series (e.g., Fibonacci, Merge Sort).
*   **Iteration:** Generally more memory efficient because it doesn't consume stack space.

## 6. Tail Recursion

Tail recursion is a special form of recursion where the recursive call is the *very last* action in the function. Some compilers (like in functional languages) can optimize this into a loop to prevent stack overflow (Tail Call Optimization). Python and Java generally do not support this optimization.

## 7. Memoization

Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. It is particularly useful in recursive algorithms that have overlapping subproblems.

### Example: Fibonacci with Memoization

```python
memo = {}

def fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]
```

[[programming/functions-and-scope]]
[[programming/stacks-and-queues]]
[[programming/algorithms]]
[[programming/dynamic-programming]]