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

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

---

Why Recursion Instead of Loops?

In imperative programming, you might write:

# Imperative loop
result = 1
for i in range(1, 6):
    result *= i

This uses a mutable variable (result) that changes each iteration. In pure functional programming, variables cannot be reassigned, so recursion is used instead.

Feature	Loops (Imperative)	Recursion (Functional)
State management	Mutable counter and accumulator	Arguments carry state
Termination	Loop condition	Base case
Side effects	Variable mutation	None (pure recursion)

---

Common Recursive Patterns

Sum of a List

sumList :: [Int] -> Int
sumList [] = 0                    -- base case: empty list
sumList (x:xs) = x + sumList xs   -- recursive case: head + sum of tail

sumList [1, 2, 3, 4, 5]    -- 15

Length of a List

lengthList :: [a] -> Int
lengthList [] = 0
lengthList (_:xs) = 1 + lengthList xs

lengthList [10, 20, 30]    -- 3

Fibonacci Sequence

fibonacci :: Int -> Int
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)