Recursion in Functional Programming

In functional programming, recursion replaces loops as the primary mechanism for repetition. Since FP discourages mutable state (no loop counters that change), recursive functions call themselves with modified arguments until a base case is reached.

---

What is Recursion?

Recursion occurs when a function calls itself. Every recursive function needs:

1. Base case(s): The condition(s) under which the function stops calling itself and returns a direct result.
2. Recursive case(s): The condition(s) under which the function calls itself with modified arguments, moving toward the base case.

Simple Example — Factorial

The factorial of n (written n!) is:

• 0! = 1 (base case)
• n! = n * (n - 1)! (recursive case)

Haskell:

factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)

factorial 5    -- 5 * 4 * 3 * 2 * 1 * 1 = 120

Python:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

factorial(5)    # 120

Tracing the Recursion