Master Recursion in Python: Factorial, Fibonacci, and Pitfalls

1. What Is a Recursive Function?

A function that calls itself within its own definition is called a recursive function.

2. How Recursive Calls Work

Recursive functions execute on the call stack, consuming stack memory with each call.

The size of the stack limits the maximum recursion depth.

3. Case Studies

Factorial

The factorial n! = 1 × 2 × … × n can be expressed as fact(n) = n! = (n‑1)! × n = fact(n‑1) × n. In code:

def fact(n):
    if n == 1:
        return 1
    return n * fact(n - 1)

Computing fac(6) using a similar function yields:

def fac(n):
    if n==1:
        return 1
    else:
        res = n * fac(n-1)
        return res
print(fac(6))

Result:

Fibonacci Sequence

The sequence 1, 1, 2, 3, 5, 8, 13, 21, 34… starts with two 1s, and each subsequent term is the sum of the two preceding terms.

def fab(n):  # Fibonacci
    if n in [1, 2]:
        return 1
    return fab(n - 1) + fab(n - 2)

print(fab(1))
print(fab(2))
print(fab(8))
print(fab(13))

Result:

Advantages of Recursive Functions

Recursive definitions are simple and logically clear. Although any recursive function can be rewritten iteratively, loops often appear less intuitive.

Recursion depth must be managed because each call consumes stack space; excessive depth leads to stack overflow. For example, calculating fac(10000) on a typical machine will overflow the stack. print(fac(10000)) Result:

4. Summary

The article, based on basic Python, notes that the standard interpreter does not optimize tail recursion, so all recursive functions risk stack overflow. It discusses the pros (simple, clear logic) and cons (potential overflow) of recursion, and mentions that languages with tail‑recursion optimization can avoid this issue, as tail recursion is equivalent to loops.