Python Recursion

1. Basic Recursive Function

def print_numbers(n):
    if n == 0:
        return
    print(n)
    print_numbers(n - 1)

print_numbers(5)

A recursive function calls itself to solve a smaller instance of the same problem.

---

2. Base Case and Recursive Case

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

print(factorial(5))  # Output: 120

Every recursive function must define a base case to prevent infinite calls.

---

3. Recursive Sum of Numbers

def sum_n(n):
    if n == 1:
        return 1
    return n + sum_n(n - 1)

print(sum_n(5))  # Output: 15

Demonstrates problem decomposition through recursion.

---

4. Recursive Fibonacci Series

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

print(fibonacci(6))  # Output: 8

Classic example of overlapping subproblems in recursion.

---

5. Recursion vs Iteration Comparison

def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

print(factorial_iterative(5))  # 120

Iteration often provides better performance and memory efficiency than deep recursion.

---

6. Recursive Traversal of List

def print_list(lst):
    if not lst:
        return
    print(lst[0])
    print_list(lst[1:])

print_list([1, 2, 3, 4])

Recursion is useful for navigating hierarchical or nested data.

---

7. Recursive String Reversal

def reverse_string(text):
    if len(text) == 0:
        return text
    return reverse_string(text[1:]) + text[0]

print(reverse_string("Python"))  # Output: nohtyP

Illustrates recursive manipulation of sequences.

---

8. Recursion Limit Error

def infinite_recursion():
    return infinite_recursion()

# infinite_recursion()  # Raises RecursionError

Python enforces a recursion limit to prevent stack overflow.

---

9. Checking Recursion Depth

import sys

print(sys.getrecursionlimit())  # Default ~1000

System recursion limits can be queried and adjusted cautiously.

---

10. Optimizing Recursion with Memoization

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(30))  # Optimized recursion

Memoization dramatically improves performance by caching results.

---