Programming Techniques

Recursion & Tail Recursion

Solving problems by reducing them to simpler versions of themselves, and how to do it without blowing the stack.

Overview

Recursion is a technique where a function calls itself to solve a smaller version of the same problem. It is the natural fit for tree traversal, divide-and-conquer algorithms, and any problem with a self-similar structure. Tail recursion is a special form where the recursive call is the very last operation, enabling compilers and runtimes to reuse the current stack frame rather than growing the stack.

Origin

Formal recursion theory was developed by Alonzo Church and Alan Turing in the 1930s as part of lambda calculus and computability theory. It entered programming through LISP (1958), which relied on it as the primary control-flow mechanism.

Examples

Tree traversal with recursion

function sumTree(node) {
  if (node === null) return 0
  return node.value + sumTree(node.left) + sumTree(node.right)
}

// Tail-recursive accumulator version (avoids stack growth)
function sumTreeTail(node, acc = 0) {
  if (node === null) return acc
  // Note: true tail recursion requires trampolining in JS
  // since the engine must process both branches
  return sumTreeTail(node.left, acc + node.value) + sumTreeTail(node.right, 0)
}

Binary trees cannot be traversed with a single tail call because both branches must be explored. True tail-recursive tree traversal requires converting one branch to an explicit stack.

Trampolining to avoid stack overflow in Ruby

# Ruby does not optimise tail calls by default.
# Trampolining converts recursion to a loop.

def trampoline(f, *args)
  result = f.call(*args)
  while result.is_a?(Proc)
    result = result.call
  end
  result
end

factorial = lambda do |n, acc = 1|
  return acc if n <= 1
  -> { factorial.call(n - 1, n * acc) }  # return a thunk
end

trampoline(factorial, 10_000)  # no stack overflow

Each step returns a lambda (thunk) rather than calling itself. The trampoline loop evaluates each thunk until a non-lambda result arrives.

Use Cases

01Traversing trees, graphs, and nested data structures (file systems, ASTs, DOM)
02Divide-and-conquer algorithms: merge sort, quicksort, binary search
03Backtracking problems: mazes, permutations, Sudoku solvers
04Parsing recursive grammars and expression evaluators
05Flattening or transforming arbitrarily nested data

When Not to Use

//When the input depth is unbounded and the runtime does not optimise tail calls, a loop is safer
//For simple counting or accumulation tasks where iteration reads more clearly
//When the recursive depth regularly exceeds a few thousand levels in languages without tail-call optimisation
//When performance is critical: function call overhead accumulates in deeply recursive paths

Technical Notes

Ruby enables tail-call optimisation only when RubyVM::InstructionSequence.compile_option = { tailcall_optimization: true } is set explicitly
JavaScript (V8) had TCO in strict mode briefly but removed it. Use trampolines for guaranteed safety
Memoisation (see the Memoization topic) and recursion combine naturally, this is the essence of dynamic programming
Mutual recursion (A calls B, B calls A) can be harder to reason about; prefer converting one function to an explicit state machine if the relationship becomes complex
In Elixir and Haskell, tail-call recursion is the standard loop construct, there are no explicit loop keywords