DSA — Recursion

What is Recursion?

A function that calls itself to solve smaller instances of the same problem.

def factorial(n):
    if n == 0:  # Base case
        return 1
    return n * factorial(n - 1)  # Recursive case

print(factorial(5))  # 120

Base Case vs Recursive Case

Case	Description
Base case	Stops recursion
Recursive case	Continues recursion

How Recursion Works

factorial(5)
  → 5 * factorial(4)
    → 4 * factorial(3)
      → 3 * factorial(2)
        → 2 * factorial(1)
          → 1 * factorial(0)
            → returns 1
          → returns 1
        → returns 2
      → returns 6
    → returns 24
  → returns 120

Common Recursion Examples

# Fibonacci
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

# Power
def power(base, exp):
    if exp == 0:
        return 1
    return base * power(base, exp - 1)

# Sum of digits
def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)

Tail Recursion

def factorial_tail(n, acc=1):
    if n == 0:
        return acc
    return factorial_tail(n - 1, n * acc)

Mini Practice

1. Write factorial recursively
2. Implement fibonacci
3. Create a recursive power function
4. Solve a recursive problem

Up Next

Continue with Arrays — array data structure.