5.0  Prologue

In purely functional languages, there are no mutable loop variables, so iteration is expressed as recursion. Far from being a limitation, recursion makes the structure of the computation mirror the structure of the data. A function that processes a list naturally splits into the head case and the tail case; a function that processes a tree splits into the leaf case and the branch case.

5.1  Structural Recursion

Structural recursion is recursion that follows the shape of the data type. Each recursive call is made on a structurally smaller piece of the input. This guarantees termination: the input shrinks at each step until a base case is reached. -- Haskell: structural recursion over a list length' :: [a] -> Int length' [] = 0 -- base case: empty list length' (_:xs) = 1 + length' xs -- step: recurse on the tail sum' :: Num a => [a] -> a sum' [] = 0 sum' (x:xs) = x + sum' xs -- Structural recursion over a binary tree data Tree a = Leaf | Node (Tree a) a (Tree a) depth :: Tree a -> Int depth Leaf = 0 depth (Node l _ r) = 1 + max (depth l) (depth r) Structural recursion is the definitional style for processing ADTs. Proof assistants and dependently typed languages require structural recursion to guarantee that programs terminate.

5.2  Mutual Recursion

Mutual recursion occurs when two or more functions call each other. It is the natural expression of mutually defined concepts - for example, checking whether a number is even or odd by delegation. -- Haskell: mutually recursive functions (both in scope simultaneously) isEven :: Int -> Bool isEven 0 = True isEven n = isOdd (n - 1) isOdd :: Int -> Bool isOdd 0 = False isOdd n = isEven (n - 1) -- F#: mutual recursion requires 'and' keyword let rec isEven n = if n = 0 then true else isOdd (n - 1) and isOdd n = if n = 0 then false else isEven (n - 1) -- Rust: forward declarations not needed; all items in a module are mutually visible fn is_even(n: u32) -> bool { if n == 0 { true } else { is_odd(n - 1) } } fn is_odd (n: u32) -> bool { if n == 0 { false } else { is_even(n - 1) } }

5.3  Corecursion and Infinite Structures

Corecursion is the dual of recursion. While recursion decomposes a finite structure to a base case, corecursion generates a potentially infinite structure one step at a time. In lazy languages, infinite structures are safe because only the demanded portion is evaluated. -- Haskell: infinite list of natural numbers (lazy; only what's demanded is computed) nats :: [Int] nats = [0..] -- or equivalently: 0 : map (+1) nats -- Infinite Fibonacci sequence fibs :: [Integer] fibs = 0 : 1 : zipWith (+) fibs (tail fibs) take 10 fibs -- [0,1,1,2,3,5,8,13,21,34] -- Infinite stream of primes via the Sieve of Eratosthenes primes :: [Int] primes = sieve [2..] where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0] In strict languages (Rust, Python), infinite sequences must be represented explicitly as iterators or generators. Haskell’s lazy evaluation makes corecursion the natural idiom for streams. -- Rust: infinite iterator via unfold use std::iter; let nats = iter::successors(Some(0u64), |&n| Some(n + 1)); let first_10: Vec<_> = nats.take(10).collect(); -- Python: generator function def nats(): n = 0 while True: yield n n += 1

5.4  Tail Call Optimization

A tail call is a function call that is the very last action of the calling function; its result is returned directly without further computation. Tail call optimization (TCO) converts such calls into jumps, reusing the current stack frame and enabling bounded-stack recursion over arbitrarily large inputs. -- Haskell: GHC performs TCO automatically -- Tail-recursive accumulator pattern factTail :: Integer -> Integer -> Integer factTail 0 acc = acc factTail n acc = factTail (n - 1) (n * acc) factorial :: Integer -> Integer factorial n = factTail n 1 -- F#: tail-recursive; F# guarantees TCO for self-tail-calls let rec factTail n acc = if n = 0 then acc else factTail (n - 1) (n * acc) -- Rust: TCO not guaranteed; use explicit loop for stack safety fn factorial(n: u64) -> u64 { let mut acc = 1; let mut i = n; while i > 0 { acc *= i; i -= 1; } acc } Haskell and F# guarantee TCO for direct tail calls. Scheme (R7RS) mandates it. Python explicitly disallows TCO as a design decision (Guido van Rossum: stack traces must be readable). Rust does not guarantee it. For deep recursion in languages without TCO, convert to an explicit accumulator loop or use a trampoline.

5.5  Epilogue

Recursion in declarative languages is not a workaround for lacking loops - it is the appropriate tool for processing recursive data structures. Structural recursion mirrors the data; corecursion generates it; TCO makes deep recursion safe. The next chapter covers combinators, the library of reusable higher-order functions that handle the most common recursion patterns so you rarely need to write them explicitly.

5.6  References

Structural Induction - Wikipedia
Corecursion - Wikipedia
Tail Call - Wikipedia
Rust iter::successors