Recursion in Python Explained — How It Works, When to Use It, and When to Avoid It

import sys

def countdown(current_number):
    """
    Counts down from current_number to 1, then prints 'Go!'.
    Each recursive call gets its own 'current_number' variable on the stack.
    """
    # BASE CASE — the simplest version of the problem we can answer directly.
    # Without this, the function would call itself forever and hit RecursionError.
    if current_number == 0:
        print("Go!")
        return  # stops the recursion and starts unwinding the stack

    # RECURSIVE CASE — we print the current number, then ask the function
    # to handle the rest of the countdown (current_number - 1).
    print(f"Stack depth: {current_number} | Calling countdown({current_number - 1})")
    countdown(current_number - 1)

    # This line runs AFTER the recursive call returns.
    # It proves the original call was paused, not destroyed.
    print(f"Stack depth: {current_number} | Back from countdown({current_number - 1}) — unwinding")

print(f"Python's default recursion limit: {sys.getrecursionlimit()}")
print("--- Starting countdown ---")
countdown(3)

import os
import functools
import time

# ─────────────────────────────────────────────
# EXAMPLE 1: Factorial — the pattern template
# ─────────────────────────────────────────────
def factorial(number):
    """
    Returns the factorial of a non-negative integer.
    factorial(5) → 5 × 4 × 3 × 2 × 1 = 120
    """
    if number < 0:
        raise ValueError(f"Factorial is not defined for negative numbers, got {number}")

    # Base case: 0! and 1! are both defined as 1
    if number <= 1:
        return 1

    # Recursive case: n! = n × (n-1)!
    # We trust that factorial(number - 1) will return the right answer —
    # this trust is what makes recursion work. Focus on one level at a time.
    return number * factorial(number - 1)

print("=== Factorial ===")
for n in [0, 1, 5, 10]:
    print(f"  factorial({n}) = {factorial(n)}")


# ─────────────────────────────────────────────
# EXAMPLE 2: Fibonacci — naive vs memoised
# ─────────────────────────────────────────────
def fibonacci_naive(position):
    """
    Returns the Fibonacci number at the given position.
    fibonacci(0)=0, fibonacci(1)=1, fibonacci(6)=8
    WARNING: exponential time complexity O(2^n). Melts for n > 35.
    """
    if position <= 0:
        return 0
    if position == 1:
        return 1
    # This creates a binary tree of calls. fibonacci(6) calls fibonacci(5)
    # AND fibonacci(4). fibonacci(5) also calls fibonacci(4). That's wasteful.
    return fibonacci_naive(position - 1) + fibonacci_naive(position - 2)

# @lru_cache stores results so we never compute the same position twice.
# This converts the time complexity from O(2^n) to O(n). One decorator, massive gain.
@functools.lru_cache(maxsize=None)
def fibonacci_memoised(position):
    """Same logic as naive, but results are cached after the first call."""
    if position <= 0:
        return 0
    if position == 1:
        return 1
    return fibonacci_memoised(position - 1) + fibonacci_memoised(position - 2)

print("\n=== Fibonacci: Naive vs Memoised ===")
test_position = 35

start = time.perf_counter()
naive_result = fibonacci_naive(test_position)
naive_duration = time.perf_counter() - start

start = time.perf_counter()
memo_result = fibonacci_memoised(test_position)
memo_duration = time.perf_counter() - start

print(f"  fibonacci({test_position}) = {naive_result}")
print(f"  Naive time:     {naive_duration:.4f}s")
print(f"  Memoised time:  {memo_duration:.6f}s")
print(f"  Speedup:        ~{naive_duration / memo_duration:.0f}x faster")


# ─────────────────────────────────────────────
# EXAMPLE 3: Recursive file system walk
# This is real production-style recursion.
# ─────────────────────────────────────────────
def list_python_files(directory_path, indent_level=0):
    """
    Recursively lists all .py files under directory_path,
    showing folder structure with indentation.
    """
    indent = "  " * indent_level  # visual depth indicator

    try:
        entries = os.listdir(directory_path)
    except PermissionError:
        print(f"{indent}[Permission denied: {directory_path}]")
        return  # graceful base case — can't go deeper, so stop

    for entry_name in sorted(entries):
        full_path = os.path.join(directory_path, entry_name)

        if os.path.isdir(full_path):
            # It's a folder — recurse into it, one level deeper
            print(f"{indent}📁 {entry_name}/")
            list_python_files(full_path, indent_level + 1)

        elif entry_name.endswith(".py"):
            # It's a Python file — base case, just print it
            size_kb = os.path.getsize(full_path) / 1024
            print(f"{indent}  🐍 {entry_name} ({size_kb:.1f} KB)")

print("\n=== Python Files in Current Directory ===")
list_python_files(".")

# Comparing recursive and iterative approaches for two problems.
# Problem A: Sum a flat list — iteration wins clearly.
# Problem B: Flatten a deeply nested list — recursion wins clearly.

from typing import Any

# ─────────────────────────────────────────────
# PROBLEM A: Summing a flat list
# ─────────────────────────────────────────────
def sum_recursive(number_list):
    """Recursive sum — technically works, but awkward for a flat list."""
    if not number_list:          # base case: empty list sums to zero
        return 0
    # Take the first element, add it to the sum of everything else.
    # Python creates a new list slice on every call — that's O(n²) memory.
    return number_list[0] + sum_recursive(number_list[1:])

def sum_iterative(number_list):
    """Iterative sum — this is how you should actually do it."""
    running_total = 0
    for number in number_list:   # O(n) time, O(1) extra memory
        running_total += number
    return running_total

sample_numbers = [10, 20, 30, 40, 50]
print("=== Flat List Sum ===")
print(f"  Recursive: {sum_recursive(sample_numbers)}")   # works, but wasteful
print(f"  Iterative: {sum_iterative(sample_numbers)}")   # clean and efficient
print(f"  Built-in:  {sum(sample_numbers)}")             # just use this in real life


# ─────────────────────────────────────────────
# PROBLEM B: Flattening an arbitrarily nested list
# ─────────────────────────────────────────────
def flatten_nested_list(nested: Any) -> list:
    """
    Converts an arbitrarily nested list into a flat list.
    flatten_nested_list([1, [2, [3, 4]], 5]) → [1, 2, 3, 4, 5]

    The iterative version of this requires manually managing a stack.
    The recursive version just... describes what flat means.
    """
    flat_result = []

    for item in nested:
        if isinstance(item, list):
            # This item is itself a list — recurse into it.
            # We don't know how deep it goes, and we don't need to.
            flat_result.extend(flatten_nested_list(item))
        else:
            # Base case: it's a plain value, just collect it.
            flat_result.append(item)

    return flat_result

weirdly_nested = [1, [2, 3], [4, [5, [6, 7]]], 8, [9, [10]]]
print("\n=== Flatten Nested List ===")
print(f"  Input:  {weirdly_nested}")
print(f"  Output: {flatten_nested_list(weirdly_nested)}")

# For contrast, here's what the iterative version looks like.
# It's correct, but you have to manage the stack manually — more surface area for bugs.
def flatten_iterative(nested: Any) -> list:
    """Iterative flatten using an explicit stack. Compare complexity with above."""
    flat_result = []
    stack = list(nested)         # seed the stack with top-level items

    while stack:
        item = stack.pop(0)      # take from the front to preserve order
        if isinstance(item, list):
            stack = list(item) + stack   # push inner items back onto the front
        else:
            flat_result.append(item)

    return flat_result

print(f"  Iterative output: {flatten_iterative(weirdly_nested)}")
print("  Both give the same result. Recursive version is easier to reason about.")