R Recursive Functions

A recursive function calls itself during execution. It solves a complex problem by breaking it down into a smaller version of the same problem, calling itself with that smaller input, and stopping when it reaches a base case — a simple condition that produces an answer without further recursion.

The Recipe for Any Recursive Function

recursive_fn <- function(input) {
  # Step 1: Base case (stop condition)
  if (input reaches simplest form) {
    return(simple answer)
  }

  # Step 2: Recursive call (smaller problem)
  return(recursive_fn(smaller input))
}

Example 1: Factorial

factorial_r <- function(n) {
  if (n == 0 || n == 1) return(1)   # base case
  return(n * factorial_r(n - 1))    # recursive call
}

factorial_r(5)   # 120

Call stack for factorial_r(5):
  factorial_r(5) = 5 × factorial_r(4)
                       = 4 × factorial_r(3)
                             = 3 × factorial_r(2)
                                   = 2 × factorial_r(1)
                                               = 1  ← base case
  Unwinding: 2×1=2 → 3×2=6 → 4×6=24 → 5×24=120

Example 2: Fibonacci Sequence

fibonacci <- function(n) {
  if (n == 1) return(0)   # F(1) = 0
  if (n == 2) return(1)   # F(2) = 1
  return(fibonacci(n - 1) + fibonacci(n - 2))
}

fibonacci(7)   # 8  (sequence: 0,1,1,2,3,5,8,13,...)
sapply(1:8, fibonacci)   # 0 1 1 2 3 5 8 13

Example 3: Sum of a Vector

my_sum <- function(v) {
  if (length(v) == 0) return(0)           # base case
  return(v[1] + my_sum(v[-1]))            # first element + rest
}

my_sum(c(10, 20, 30, 40))   # 100

Example 4: Flatten a Nested List

flatten <- function(lst) {
  result <- c()
  for (item in lst) {
    if (is.list(item)) {
      result <- c(result, flatten(item))  # recurse into sub-list
    } else {
      result <- c(result, item)
    }
  }
  return(result)
}

nested <- list(1, list(2, 3), list(4, list(5, 6)))
flatten(nested)   # 1 2 3 4 5 6

Recursion vs Iteration

          Recursion              Iteration (Loop)
──────────────────────────────────────────────────────
Elegant for tree-like data     Faster for simple repetition
Can run deep (stack limit)     No stack depth limit in R
Can be slower (overhead)       Generally more efficient in R
Mirrors mathematical def.      Straightforward to debug

Stack Overflow Risk

R has a recursion depth limit (around 700-1000 calls by default). Calling a recursive function with a very large input exceeds this limit.

# This will error if n is very large
factorial_r(10000)   # Error: C stack usage is too close to the limit

For large inputs, convert to a loop. For moderate inputs, recursion is fine and often cleaner.

Memoization: Speed Up Recursive Functions

library(memoise)

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

fib_memo(30)   # fast — previously computed values are cached

Use recursion when the problem naturally decomposes into smaller identical subproblems — tree traversal, nested data flattening, mathematical sequences, divide-and-conquer algorithms. For flat, repetitive tasks on large data, prefer loops or vectorized operations.