22  Recursion and fixed points

Suppose you need to process a tree of unknown depth, a structure that nests inside itself with no predetermined bottom. A for loop can’t express this because you don’t know how many levels to iterate; you would need a loop inside a loop inside a loop, with no way to say how many.

The alternative is a function that calls itself, peeling away one layer of nesting each time until it reaches something solid. Reduce() in Chapter 21 was one specific pattern of this kind. The general form can express anything a loop can, and several things loops express awkwardly. What happens, though, when the chain of self-calls grows too long for R to handle?

22.1 Recursive functions

The simplest case is the one every textbook reaches for: the factorial. n! = n * (n-1) * … * 1, with 0! = 1:

factorial_r <- function(n) {
  if (n == 0) return(1)
  n * factorial_r(n - 1)
}

factorial_r(6)
#> [1] 720

factorial_r calls itself, which makes it a recursive function. The definition sounds circular, and the circularity is the point: the problem for 6 is solved by way of the problem for 5, which is solved by way of the problem for 4, down to a problem small enough to answer directly. Two parts make this work. A base case stops the recursion (n == 0 here), and a recursive case makes progress toward it (n - 1 is closer to 0 than n was). Forget the base case and the calls never stop, which in R ends in a stack overflow error.

Fibonacci numbers are the other classic:

fib <- function(n) {
  if (n <= 1) return(n)
  fib(n - 1) + fib(n - 2)
}

sapply(0:10, fib)
#>  [1]  0  1  1  2  3  5  8 13 21 34 55

This works, and it is slow: each call spawns two more, so the running time is O(2^n) (Chapter 9), and fib(30) alone makes about 2.7 million calls. Memoization (Section 20.4) or an accumulator (later in this chapter) fixes that. Performance aside, there is a more basic question. Does a recursive function even need a name?

Recall() calls the current function without naming it:

(function(n) {
  if (n == 0) return(1)
  n * Recall(n - 1)
})(6)
#> [1] 720

R looks up the function that is currently executing on the call stack, so Recall() works even inside an anonymous function. In practice, named functions are clearer, but Recall() occasionally appears in one-off recursive helpers passed to higher-order functions.

Exercises

1. Write a recursive function sum_to(n) that computes 1 + 2 + … + n. What is the base case?
2. Write a recursive function power_r(x, n) that computes x^n using repeated multiplication. Handle the case n = 0.
3. The naive fib() recomputes the same values many times. Use memoise::memoise() to create fib_memo and compare system.time(fib(30)) with system.time(fib_memo(30)).

22.2 The call stack

Every time R calls a function, it creates a new frame on the call stack: a record of the function, its arguments, and its local variables (each frame corresponds to the execution environment from Section 18.3). When the function returns, its frame is popped. Recursive calls pile up frames like plates on a spring-loaded stack, and you can watch it happen:

factorial_traced <- function(n) {
  cat("Entering n =", n, "at depth", sys.nframe(), "\n")
  if (n == 0) return(1)
  result <- n * factorial_traced(n - 1)
  cat("Returning", result, "for n =", n, "\n")
  result
}

factorial_traced(4)
#> Entering n = 4 at depth 31 
#> Entering n = 3 at depth 32 
#> Entering n = 2 at depth 33 
#> Entering n = 1 at depth 34 
#> Entering n = 0 at depth 35 
#> Returning 1 for n = 1 
#> Returning 2 for n = 2 
#> Returning 6 for n = 3 
#> Returning 24 for n = 4
#> [1] 24

sys.nframe() returns the current depth of the call stack, and each recursive call adds one frame. For factorial_traced(4), the stack grows to depth 4 (plus whatever depth the calling context contributes), then unwinds as each call returns its result back up the chain.

R imposes a limit on this depth. The default is 5,000 nested evaluations, controlled by options(expressions = ...), and if you exceed it you get one of two messages:

Error: evaluation nested too deeply: infinite recursion / options(expressions=)?

or, when the C stack fills up first:

Error: C stack usage <number> is too close to the limit

The limit is there to stop infinite recursion from crashing your R session. If your algorithm needs more than a few thousand levels, restructure the algorithm rather than raising the number.

# This will error:
count_down <- function(n) {
  if (n == 0) return(0)
  count_down(n - 1)
}
count_down(10000)

Exercises

1. Call factorial_traced(5) and note the depth values. Then call factorial_traced(5) from inside another function. How do the depths change?
2. What is the default value of getOption("expressions")? Try setting it to 100 and calling count_down(200). What error do you get?

22.3 Tail recursion and accumulators

Look at factorial_r one more time:

factorial_r <- function(n) {
  if (n == 0) return(1)
  n * factorial_r(n - 1)
}

After the recursive call returns, there is still work left: multiply the result by n. That pending multiplication means R cannot discard the current frame while waiting for the recursion to bottom out; every single frame in the chain must stay alive, holding onto its local n, until the deepest call finally returns 1 and the whole tower of deferred multiplications collapses upward.

A tail-recursive version eliminates that pending work by threading the partial answer through an accumulator argument, so the recursive call becomes the very last operation the function performs:

factorial_tail <- function(n, acc = 1) {
  if (n == 0) return(acc)
  factorial_tail(n - 1, acc * n)
}

factorial_tail(6)
#> [1] 720

When the recursive call sits in tail position (nothing happens after it), a compiler can reuse the current frame instead of allocating a new one, converting O(n) stack usage to O(1). This is tail-call optimization (TCO). Scheme guarantees it and Haskell effectively provides it, but R does not, so factorial_tail(10000) still hits the evaluation limit even though the function is logically a loop.

The accumulator pattern is still worth having. It makes the intent visible (the accumulator carries the “answer so far”), it is the prerequisite for trampolining (next section), and it can convert exponential algorithms into linear ones. Here is Fibonacci rewritten with two accumulators, running in linear time instead of exponential:

fib_tail <- function(n, a = 0, b = 1) {
  if (n == 0) return(a)
  fib_tail(n - 1, b, a + b)
}

fib_tail(30)
#> [1] 832040

Where the naive fib() needed millions of calls for fib(30), this version makes exactly n. But it still can’t survive fib_tail(10000) on R’s stack. What if we could get the O(1) stack usage ourselves, without waiting for a language feature R will never add?

Exercises

1. Write a tail-recursive sum_to_tail(n, acc = 0) that computes 1 + 2 + … + n.
2. Write a tail-recursive reverse_list(x, acc = list()) that reverses a list.
3. Verify that factorial_tail(5000) still errors. Why can R not optimize this?

22.4 Trampolining

Since R will not optimize tail calls, you can do it by hand. Instead of making the recursive call, return a zero-argument function that represents the call you would have made:

factorial_thunk <- function(n, acc = 1) {
  if (n == 0) return(acc)
  function() factorial_thunk(n - 1, acc * n)
}

Calling factorial_thunk(10) now returns a function rather than a number. A loop keeps calling whatever comes back until the result is no longer a function:

trampoline <- function(f, ...) {
  result <- f(...)
  while (is.function(result)) {
    result <- result()
  }
  result
}

trampoline(factorial_thunk, 10)
#> [1] 3628800
trampoline(factorial_thunk, 1000)
#> [1] Inf

That second call goes through 1,000 iterations without growing the stack at all. Each “recursive” step returns a closure and the while loop calls it, so control bounces between the two like a ball on a trampoline. The zero-argument function is a thunk, the loop is the trampoline, and stack depth stays at O(1) no matter how deep the logical recursion goes.

The pattern works for any tail-recursive function: rewrite the tail call as a thunk and let the trampoline do the looping. The cost is one closure allocation per step. The CRAN package trampoline provides an implementation with better error handling, but the core idea is exactly this while loop.

TipOpinion

Trampolining is clever, but if you catch yourself trampolining in production R code, pause and ask whether a for loop or Reduce() would be simpler. The trampoline rescues recursive algorithms from the stack limit; it does not replace straightforward iteration. Save it for cases where you genuinely need recursion (tree traversal of unknown depth, for instance) but the depth could be large.

Exercises

1. Convert fib_tail into a trampolined version. Compute fib(100000) without a stack overflow. (The number will be huge; just verify it completes.)
2. The trampoline function above has a subtle limitation: it cannot return a function as a final result (since functions trigger another iteration). How would you fix this? Hint: wrap the final result in a special marker.

22.5 Divide and conquer

Some problems split cleanly in half, and each half looks just like the original problem, only smaller. Split, solve each piece recursively, combine. This is the divide and conquer strategy, and recursion expresses it so naturally that the code almost reads like the definition.

Merge sort is the cleanest example: split the vector in half, sort each half, merge the sorted halves back together:

merge_sort <- function(x) {
  if (length(x) <= 1) return(x)

  mid <- length(x) %/% 2
  left  <- merge_sort(x[1:mid])
  right <- merge_sort(x[(mid + 1):length(x)])

  merge_sorted(left, right)
}

merge_sorted <- function(a, b) {
  result <- numeric(length(a) + length(b))
  i <- j <- k <- 1
  while (i <= length(a) && j <= length(b)) {
    if (a[i] <= b[j]) {
      result[k] <- a[i]; i <- i + 1
    } else {
      result[k] <- b[j]; j <- j + 1
    }
    k <- k + 1
  }
  while (i <= length(a)) { result[k] <- a[i]; i <- i + 1; k <- k + 1 }
  while (j <= length(b)) { result[k] <- b[j]; j <- j + 1; k <- k + 1 }
  result
}

merge_sort(c(5, 2, 8, 1, 9, 3))
#> [1] 1 2 3 5 8 9

Each level of recursion halves the problem, giving O(log n) levels, and each level does O(n) work merging, so the total comes to O(n log n) as discussed in Chapter 9. The recursion depth is only log2(n), which means even a million-element vector needs just 20 levels. Balanced divide-and-conquer algorithms stay far below the evaluation limit; the branching that makes them fast also keeps them shallow.

Binary search follows the same pattern but only recurses into one half:

binary_search <- function(x, target, lo = 1, hi = length(x)) {
  if (lo > hi) return(NA)
  mid <- (lo + hi) %/% 2
  if (x[mid] == target) return(mid)
  if (x[mid] < target) binary_search(x, target, mid + 1, hi)
  else binary_search(x, target, lo, mid - 1)
}

binary_search(1:100, 73)
#> [1] 73

Exercises

1. Trace through merge_sort(c(4, 1, 3, 2)) on paper. How many recursive calls are made?
2. Write a recursive function tree_depth that takes a nested list and returns its maximum depth. tree_depth(list(1, list(2, list(3)))) should return 3.

22.6 Recursive list processing

Nested lists are R’s tree structure, and recursion is the natural way to walk them. Suppose you need to extract all numeric values buried somewhere inside an arbitrarily nested list, and you don’t know how deep the nesting goes or where the numbers are:

find_numbers <- function(x) {
  if (is.numeric(x)) return(x)
  if (!is.list(x)) return(NULL)
  unlist(lapply(x, find_numbers))
}

nested <- list("a", list(1, list("b", 2, list(3, "c"))))
find_numbers(nested)
#> [1] 1 2 3

The function dispatches on type: numbers come back directly, non-list non-numbers get discarded, and lists trigger a recursive lapply that peels off one layer at a time. unlist(nested) would have flattened the same list, but it coerces everything to one type and keeps every leaf; the hand-written version keeps only what you ask for. “Check the base cases, recurse on the structure” is the shape of all tree-processing code.

Base R provides rapply() for recursive application over lists:

rapply(nested, sqrt, classes = "numeric", how = "unlist")
#> [1] 1.000000 1.414214 1.732051

rapply() walks the nested structure, applies sqrt to every numeric element it encounters, and returns the results. The classes argument filters which elements get processed, and how controls the output shape (“unlist”, “replace”, or “list”).

rapply(nested, toupper, classes = "character", how = "replace")
#> [[1]]
#> [1] "A"
#> 
#> [[2]]
#> [[2]][[1]]
#> [1] 1
#> 
#> [[2]][[2]]
#> [[2]][[2]][[1]]
#> [1] "B"
#> 
#> [[2]][[2]][[2]]
#> [1] 2
#> 
#> [[2]][[2]][[3]]
#> [[2]][[2]][[3]][[1]]
#> [1] 3
#> 
#> [[2]][[2]][[3]][[2]]
#> [1] "C"

With how = "replace", the nesting is preserved: character elements are uppercased in place while everything else stays untouched. rapply() is rarely seen, partly because deeply nested lists are uncommon in day-to-day R work. If your data is a tree, it deserves a look.

Exercises

1. Write a recursive function flatten that takes a nested list and returns a flat list of its leaf elements. Compare with rapply(x, identity, how = "unlist").
2. Use rapply() with how = "replace" to double every numeric element in list(1, list("a", 2, list(3, "b"))).
3. Write a recursive function that counts the total number of leaf elements in a nested list.

22.7 Mutual recursion

Two functions can call each other, passing control back and forth. Mutual recursion appears naturally in recursive descent parsers, where each grammar rule becomes a function that may call functions for other rules, and in state machines, where each state is a function that transitions by calling another state’s function. The pattern is easier to see, though, in a stripped-down example:

is_even <- function(n) {
  if (n == 0) return(TRUE)
  is_odd(n - 1)
}

is_odd <- function(n) {
  if (n == 0) return(FALSE)
  is_even(n - 1)
}

is_even(4)
#> [1] TRUE
is_odd(7)
#> [1] TRUE

Each function delegates to the other, peeling off one layer at a time. Nobody would check parity this way, but the structure is identical to what a parser does when an expression rule calls a term rule that calls an expression rule again.

The stack cost is the same as ordinary recursion, doubled: each round trip consumes two frames. For deep mutual recursion, trampolining works identically; just have both functions return thunks instead of calling each other directly.

But mutual recursion raises a subtler question than stack depth: both is_even and is_odd refer to each other by name. The trampoline removed the stack constraint; can anything remove the naming constraint?

22.8 Fixed-point combinators

Here is an odd question. Can you write a recursive function without ever giving it a name? Named functions call themselves by name, so recursion seems to require naming. But what if you only have anonymous functions, nothing else?

Start with a factorial that does not call itself. Instead, it takes the function to call as an argument:

fact_step <- function(f) function(n) {
  if (n == 0) 1 else n * f(n - 1)
}

fact_step is a factory: hand it any function f and it returns a factorial-shaped function that delegates the smaller case to f. What it needs is to be handed itself, or rather the function it is about to return. A second function can arrange that. It takes f, and applies a function to itself:

Y <- function(f) (function(x) f(x(x)))(function(x) f(x(x)))

fact <- Y(fact_step)
fact(6)
#> [1] 720

It works. The function never names itself and never uses Recall(), yet it recurses. Follow one step to see how. Y(fact_step) calls function(x) fact_step(x(x)) with a copy of itself as x, so inside, fact_step is called with the argument x(x). R does not evaluate that argument. It hands fact_step the unevaluated expression, fact_step returns its function(n) without touching f, and that is what fact is. Only when fact(6) reaches n * f(n - 1) does R evaluate x(x), which produces one more function(n) with one more untouched f inside it. Each level of recursion forces exactly one more copy, and the chain ends when n == 0 and f is never used.

That only works because R evaluates an argument the first time it is used rather than when it is passed. In a language that computes every argument before the call, Python or JavaScript for instance, x(x) would be evaluated before f ever ran, and evaluating it means evaluating f(x(x)), whose argument is x(x) again, forever. The fix in such a language is to wrap each x(x) in a function of one argument, function(v) x(x)(v), so the self-application is delayed until someone actually calls it with a v:

Z <- function(f) {
  (function(x) f(function(v) x(x)(v)))(
    function(x) f(function(v) x(x)(v)))
}

Z(fact_step)(6)
#> [1] 720

The wrapper is a thunk with one argument, the same trick the trampoline used. Both versions run in R; only the second runs everywhere.

What these two functions compute has a name. A fixed point of a function g is a value x where g(x) = x; the number 0 is a fixed point of function(x) x^2, because 0^2 = 0. fact is a fixed point of fact_step: feeding fact back into fact_step returns a function that behaves exactly like fact. Y and Z find that fixed point for any f you give them, which is why they are called fixed-point combinators. Y is the Y combinator, and Z is the variant for languages that evaluate arguments eagerly.

NoteThe lambda calculus connection

In Church’s notation the Y combinator is

Y = λf. (λx. f (x x)) (λx. f (x x))

and the R version above is a transliteration. Lambda calculus has only three constructs: variables, abstraction (function definition), and application (function calling). There is no built-in recursion, no loop, and no assignment, and the fixed-point combinator is how recursion is derived from the other three. Chapter 30 follows this thread through Church numerals and the rest of the correspondence between lambda calculus and R.

You will never use Y or Z in production R code. But the question at the end of Section 22.7 has its answer: recursion needs nothing from the language beyond function application, and the name a recursive function calls itself by was a convenience all along.

Exercises

1. Use Y to define a recursive Fibonacci function without self-reference.
2. Apply Y to function(f) function(xs) if (length(xs) == 0) 0 else xs[[1]] + f(xs[-1]) and test it on list(1, 2, 3, 4, 5). What does this compute?
3. Make Y evaluate the self-application before calling f: Ystrict <- function(f) (function(x) { y <- x(x); f(y) })(function(x) { y <- x(x); f(y) }). What happens when you call Ystrict(fact_step)? Apply the same change to Z and explain why it survives.

22.9 When not to recurse

R stops at 5,000 nested evaluations, reuses no frames for tail calls, and pays more per function call than per vectorized operation. The shape of the data tells you whether recursion is the right tool or a trap.

Tree-shaped problems, where the structure branches and nests (nested lists, file system traversal, parsing hierarchical data, divide-and-conquer algorithms with O(log n) depth), stay well within stack limits and express naturally as recursive functions. These are recursion’s home territory.

Linear problems are a different story. Summing a vector, computing a running total, filtering elements: these are loops, Reduce() calls, or vectorized operations, and writing them recursively wastes n stack frames on something that sum() handles in a single C call.

TipOpinion

If your recursive function processes a flat sequence from left to right, it is a fold; use Reduce() or purrr::reduce() from Chapter 21. If it processes elements independently, it is a map; use lapply() or purrr::map() from Section 7.1. Reserve recursion for problems where the structure of the data is itself recursive. When the data branches, your code should too.

The table below summarizes when each approach fits:

Problem shape	Preferred approach	Why
Element-wise transformation	lapply() / map() / vectorized	No overhead, parallel-friendly
Linear fold (sum, concat, merge)	Reduce() / reduce()	Constant stack, clear intent
Tree traversal, nested structures	Recursion / rapply()	Matches the data shape
Divide and conquer (sort, search)	Recursion	O(log n) depth, natural decomposition
Deep linear recursion (>1000)	Trampoline or convert to loop	Stack limit workaround

22.10 Historical notes

The sentence that broke Hilbert’s program in 1931 (Chapter 1) said, in effect, “this statement has no proof.” To write such a sentence inside arithmetic, Gödel first had to turn statements and proofs into numbers, and then had to show that “is a proof of” was an arithmetic relation like “is divisible by.” The tool he used for the second part was a family of functions built up by exactly the pattern of factorial_r: define the value at 0 outright, and define the value at n + 1 in terms of the value at n. Addition is built that way from the successor function, multiplication from addition, and so on up to a function that checks proofs. He called them recursive functions; the name for the class today is primitive recursive. Recursion got its formal definition as a way of building every function of arithmetic out of almost nothing.

Within five years the lambda calculus and Turing’s machines had each been shown to compute exactly the functions Gödel’s recursion could, and the fixed-point combinator was part of the proof on the lambda side: a system with no recursion at all could still express every recursive function.

Recursion stayed in mathematics until LISP (Section 2.1) made recursive function calls the primary control structure of a programming language, with car, cdr, and cons making recursive list processing practical. The question that remained was cost. Landin’s SECD machine (1964) showed how to evaluate expressions with closures and recursive calls mechanically, and a decade later Steele and Sussman’s “Lambda the Ultimate” papers (1975-1980) showed that a tail call is a goto with arguments, so a compiler can make it as cheap as a jump. Scheme (Section 2.2) guaranteed tail-call optimization as a consequence.

S was designed for interactive statistical computing, where vectorized operations do the heavy lifting, and it never adopted the guarantee. R inherited that choice, so a recursive descent past a few thousand frames needs a trampoline or a loop.

But R did make another choice about evaluation that most languages avoided, the one that let the Y combinator run: when you pass an argument to a function, R does not evaluate it immediately.