1. Recursion Basics.md

1. Recursion Basics and Base Cases

Recursion is a programming technique where a function calls itself, directly or indirectly, to solve a problem. It allows us to break down complex problems into smaller, identical sub-problems.

---

1. The Core Components of Recursion

Every recursive function must contain two essential components to execute correctly:

1. Base Case: The condition under which the function stops calling itself. Without a base case, the function will execute infinitely, leading to a stack overflow.
2. Recursive Case: The part of the function where it calls itself with modified (usually smaller/simpler) inputs, moving closer to the base case.

---

2. Visualizing Recursion with a Countdown

Let's look at a simple countdown example.

A. Non-recursive (Iterative) Approach:

def countdown_iterative(n):
    while n > 0:
        print(n)
        n -= 1
    print("Blastoff!")

B. Recursive Approach:

Input:

def countdown_recursive(n):
    # 1. Base Case
    if n <= 0:
        print("Blastoff!")
        return
    
    # 2. Work done in current step
    print(n)
    
    # 3. Recursive Case (calls itself with n-1)
    countdown_recursive(n - 1)

countdown_recursive(3)

Output:

3
2
1
Blastoff!

---

3. How the Call Stack Works

When a function is called, Python creates an activation record (or stack frame) and pushes it onto the Call Stack.

• In recursion, each self-call adds a new frame to the stack.
• The stack keeps growing until the base case is reached.
• Once the base case is reached, the functions start returning, popping frames off the stack in LIFO (Last In, First Out) order.

📍 Call Stack Lifecycle for countdown_recursive(3)

  1. STACK GROWTH (Pushing frames):
  ┌────────────────────────────────────────────────────────┐
  │ [ countdown_recursive(0) ] -> Base Case reached!       │
  │ [ countdown_recursive(1) ]                             │
  │ [ countdown_recursive(2) ]                             │
  │ [ countdown_recursive(3) ]                             │
  └────────────────────────────────────────────────────────┘
  
  2. STACK RESOLUTION (Popping frames after return):
  ┌────────────────────────────────────────────────────────┐
  │ [ countdown_recursive(0) ] -> Returns, pops off        │
  ├────────────────────────────────────────────────────────┤
  │ [ countdown_recursive(1) ] -> Returns, pops off        │
  ├────────────────────────────────────────────────────────┤
  │ [ countdown_recursive(2) ] -> Returns, pops off        │
  ├────────────────────────────────────────────────────────┤
  │ [ countdown_recursive(3) ] -> Returns, pops off        │
  └────────────────────────────────────────────────────────┘

---

4. Infinite Recursion and Recursion Limits

If you forget to write a base case, or if the recursive step never meets the base case, the program will call itself endlessly. Python prevents this from crashing your computer by setting a limit on how deep the call stack can go.

If this limit is exceeded, Python raises a RecursionError.

Input:

def infinite_hello():
    return infinite_hello()

try:
    infinite_hello()
except RecursionError as e:
    print("Error caught successfully:", e)

Output:

Error caught successfully: maximum recursion depth exceeded

Note

The default recursion limit in Python is usually 1000. You can check or change it using sys.getrecursionlimit() and sys.setrecursionlimit(), though increasing it too much can cause a real stack overflow crash.

 ⏮️ Prev        Next ⏭️