Functional Programming 101: Programming Without Side Effects

"Same input, always the same output" — referential transparency, Lisp, and recurrences, recursion, and memoization taught through Fibonacci numbers and the Tower of Hanoi

What functional languages are

Most programming languages are imperative: commands — "assign to this variable", "repeat this" — run from top to bottom, mutating state as they go. Functional languages take a different view. A program is built by evaluating expressions, out of functions that behave like mathematical functions: they take an input and return an output, and do nothing else.

In a functional language, functions are themselves values. They can be stored in variables, passed as arguments, and returned as results (this is called having first-class functions). "A function that takes a function" or "a function that builds and returns a function" are perfectly ordinary tools.

What "no side effects" means: referential transparency

Here comes the core concept. A side effect is any work a function does besides returning its value — mutating a global variable, printing to the screen, writing to a file. A function with no side effects — one that also depends on nothing outside its own inputs — returns the same output for the same input, no matter when, how often, or where it is called. This property is called referential transparency.

The benefits are tangible. First, testing is easy — you only look at inputs and outputs, and never ask what state must be set up beforehand. Second, understanding stays local — the world does not change across a function call, so code can be read piece by piece. Third, concurrency is safe — nothing shared is mutated, so computations can run side by side without stepping on each other.

"A function's meaning is determined by nothing but the relation between its input and its output" — if you have read the formal-methods content on this site, this should sound familiar: it is the same idea as writing contracts with pre- and postconditions. The fewer the side effects, the easier the input/output contract is to write and to verify.

Lisp: the oldest functional language

The ancestor of functional languages is Lisp. Devised by John McCarthy in 1958, it is — among high-level languages still in use today — second only to FORTRAN in age, and its dialects (Common Lisp, Scheme, Clojure) remain in active use.

Lisp's syntax is astonishingly small: nothing but S-expressions — parenthesized forms of (function argument argument ...). And that shape is itself the list data structure, so code and data share the same form, which makes "programs that generate programs" feel natural.

;; An S-expression: (function arg1 arg2 ...) — that is the whole syntax (+ 1 2) ; => 3 (* (+ 1 2) 4) ; => 12 (if (< 1 2) "yes" "no") ; => "yes"

The code examples below use one of the dialects, Common Lisp.

Recurrences: define a value from smaller problems

A recurrence relation defines the n-th value, or a problem of size n, using values with smaller indices or sizes. Instead of stating an answer directly, it gives a rule for building the next answer from smaller answers that are already known.

1. Base cases (known values where evaluation can stop)

F(0)=0, \qquad F(1)=1

2. Recurrence rule (build a value from smaller problems)

F(n)=F(n-1)+F(n-2), \qquad n \ge 2

A recurrence rule alone does not determine any values. A rule that only refers to smaller indices keeps moving backward unless it has a starting point. Only when combined with base cases does it determine every value uniquely.

A recurrence is a mathematical definition. Recursion is a programming mechanism in which a function calls itself to evaluate such a definition. They correspond closely but are not identical. A recursive function needs a base case that stops evaluation and a rule that moves every call closer to that base case.

A recurrence's initial conditions correspond to a recursive function's base cases, while the recurrence rule corresponds to recursive calls with smaller arguments. Recognizing this correspondence lets a mathematical definition become code directly.

Worked example: the n-th Fibonacci number

The Fibonacci sequence 0, 1, 1, 2, 3, 5, 8, 13, … is the sequence where each term is the sum of the previous two. Mathematically it is defined by a recurrence relation: F(0) = 0, F(1) = 1, F(n) = F(n−1) + F(n−2).

Here the appeal of functional languages shows itself: the mathematical definition becomes code almost verbatim.

;; The recurrence relation transcribed as-is (Common Lisp) ;; F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (defun fib (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))) (fib 10) ; => 55

The if mirrors the case split, and the recursive calls mirror the right-hand side of the recurrence. The distance between the specification (the mathematical definition) and the implementation could hardly be smaller. But a serious problem hides in this naive definition.

The problem: an explosion of repeated work

The call tree of (fib 5): (fib 5) ├─ (fib 4) │ ├─ (fib 3) │ │ ├─ (fib 2) ... │ │ └─ (fib 1) │ └─ (fib 2) ... └─ (fib 3) ├─ (fib 2) ... └─ (fib 1) (fib 3) twice, (fib 2) three times — the same work done over and over

Draw the call tree and you will find (fib 3) computed twice and (fib 2) three times — the same work done over and over. As n grows the duplication explodes exponentially, with a cost of roughly O(1.62ⁿ). Around fib 40, it becomes too slow to wait for.

Memoization: remembering what you computed

The fix is simple: store each computed result in a table, and when the same argument comes again, return it from the table instead of recomputing — this is memoization.

;; Memoized version: remember computed results in a hash table (Common Lisp) (let ((table (make-hash-table))) (defun fib-memo (n) (or (gethash n table) ; if it is in the table, return it (setf (gethash n table) ; otherwise compute and store it (if (< n 2) n (+ (fib-memo (- n 1)) (fib-memo (- n 2)))))))) (fib-memo 100) ; => 354224848179261915075 — returns instantly

Each n is now computed exactly once, and the cost drops from O(1.62ⁿ) to O(n). Even fib 100 is instant.

Memoization is safe precisely because fib has no side effects: the same input always yields the same output. Whether the answer comes from the table or from recomputation, it is the same — referential transparency is what guarantees that results may be reused. With a function whose result changes between calls, this would not work.

One honest note: writing into the table is, internally, a state change — a side effect. But since the input/output behavior seen from outside does not change, memoization is widely used in the functional world as an optimization that preserves apparent purity. Clojure even ships a standard memoize that memoizes a function in one line.

Exercise: solve the Tower of Hanoi recursively

The Tower of Hanoi is a puzzle in which disks of different sizes move among three rods. Initially every disk is stacked on source rod A with larger disks below smaller ones. Using auxiliary rod B, move the same tower to target rod C.

Tower of Hanoi with 3 disks (initial state): [=] | | [===] | | [=====] | | +-------------+ +-------------+ +-------------+ A: source B: auxiliary C: target Goal: move every disk from A to C

Move only one disk in each operation.

Only the top disk on a rod may be moved.

Never place a larger disk on top of a smaller disk.

To move the largest disk in an n-disk tower from A to C, first move the top n-1 disks from A to B. Move the largest disk to C once, then move the n-1 disks from B to C. The same n-1 problem appears twice, so the minimum move count follows the recurrence below.

\begin{aligned} T(0) &= 0, \\ T(n) &= T(n-1) + 1 + T(n-1) \\ &= 2T(n-1) + 1 \qquad (n \ge 1). \end{aligned}

Expand the recurrence one step at a time

Here, "expand" means replacing a smaller-size term inside the expression with the same recurrence. Start with three disks. The first substitution changes the two-disk case into the one-disk case, and the next changes the one-disk case into the zero-disk case. Notice that a coefficient outside parentheses multiplies every term inside.

\begin{aligned} T(3) &= 2T(2) + 1 \\ &= 2\bigl(2T(1) + 1\bigr) + 1 \\ &= 4T(1) + 2 + 1 \\ &= 4T(1) + 3 \\ &= 4\bigl(2T(0) + 1\bigr) + 3 \\ &= 8T(0) + 4 + 3 \\ &= 8 \cdot 0 + 7 \\ &= 7. \end{aligned}

The same pattern works for any number of disks. Each substitution reduces the size by one and doubles the outside coefficient. At the same time, the one move of the largest disk at each stage accumulates with successively doubled weights. After one substitution per disk, the expression reaches the zero-disk base case.

\begin{aligned} T(n) &= 2T(n-1) + 1 \\ &= 2^2T(n-2) + (2 + 1) \\ &= 2^3T(n-3) + (2^2 + 2 + 1) \\ &\ \vdots \\ &= 2^nT(0) + \left(2^{n-1} + \cdots + 2 + 1\right), \\ T(0)=0 &\ \Longrightarrow\ T(n) = \sum_{k=0}^{n-1} 2^k. \end{aligned}

Give the remaining sum a name. Double that sum and subtract the original: all intermediate terms cancel. Only the newly added final term and the initial one remain, so the sum can be determined.

\begin{aligned} S &= 1 + 2 + 4 + \cdots + 2^{n-1}, \\ 2S &= \phantom{1 + {}}2 + 4 + \cdots + 2^{n-1} + 2^n, \\ 2S-S &= 2^n - 1, \\ S &= 2^n - 1, \\ \therefore\quad T(n) &= 2^n - 1. \end{aligned}

Each substitution doubles the coefficient, which is why powers of two appear in the answer. The final subtraction of one comes from accumulating the one-move cost at each stage with successively doubled weights. Rather than memorizing the formula, follow the substitutions from the larger problem down to the base case.

$T(n)=2^n-1$

Substituting values into the closed form derived above gives 7 moves for three disks and 1,023 for ten. The legendary 64-disk version requires 18,446,744,073,709,551,615 moves: adding one disk almost doubles the work.

Exercise

Required: write a recursive Common Lisp function hanoi-moves that accepts a non-negative integer n and returns the minimum moves needed to transfer an n-disk tower from A to C. For example, hanoi-moves(3) returns 7 and hanoi-moves(10) returns 1,023.

Extension: write a separate hanoi-moves-closed-form function for the closed form derived above, then confirm that it returns the same values as the recursive version.

Show hint

Hint: do not use the closed form or expt in the required task. Zero disks take zero moves; otherwise solve the problem with one fewer disk twice and move the largest disk once between those subproblems.

Show example solutions

Solution 1: implement the recurrence recursively

;; Return the minimum moves for n Tower of Hanoi disks (Common Lisp) (defun hanoi-moves (n) (check-type n (integer 0 *)) (if (= n 0) 0 (+ (* 2 (hanoi-moves (- n 1))) 1))) (hanoi-moves 1) ; => 1 (hanoi-moves 3) ; => 7 (hanoi-moves 10) ; => 1023

The zero-disk base case returns zero moves, and the recursive branch solves the one-smaller problem twice, directly representing the recurrence. Every recursive call reduces the disk count by one, so evaluation reaches the base case after finitely many calls.

Distinguish function calls used to compute the number from the work of performing the puzzle. The recursive calls made by hanoi-moves grow in proportion to the disk count, while physically carrying out the solution still takes the number of disk moves derived above.

Solution 2: implement the closed form

;; Use the closed form T(n) = 2^n - 1 (Common Lisp) (defun hanoi-moves-closed-form (n) (check-type n (integer 0 *)) (1- (expt 2 n))) (hanoi-moves-closed-form 3) ; => 7 (hanoi-moves-closed-form 10) ; => 1023 (= (hanoi-moves 10) (hanoi-moves-closed-form 10)) ; => T (same result)

Common Lisp's expt computes a power and 1- subtracts one, so (1- (expt 2 n)) directly represents the closed form derived above. Comparing its result with the recursive version also provides a useful check.

This function does not call itself, so it does not replace the required recursion exercise. A one-expression implementation also does not imply constant running time: exponentiation and constructing a large integer still require work as n grows.

Summary

Functional languages build programs by evaluating expressions. The core is the absence of side effects — referential transparency (same input, always the same output).

Benefits: easy testing, local understanding, safe concurrency.

Lisp, born in 1958, is the oldest functional language. One syntax — the S-expression — and code and data share the same shape.

A recurrence is a mathematical definition of base cases and a recurrence rule, mirrored by a recursive function's stopping case and self-calls. Memoization reduces Fibonacci's repeated work to O(n).

The Tower of Hanoi has T(n) = 2T(n-1) + 1 = 2ⁿ-1 minimum moves. A recursive function can compute the count, while the work of actually moving the disks grows exponentially.