R Recursion

What makes a function recursive

A recursive function is simply a function that calls itself somewhere in its own body, usually with a different, typically smaller or simpler, argument than the one it received. Each call works on a slightly easier version of the problem until the pieces become trivial enough to answer directly.

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

factorial_r(5)

Why every recursive function needs a base case

The base case is the condition that stops the recursion, in the factorial example it's n <= 1. Without it, factorial_r would keep calling itself with smaller and smaller values of n forever, since nothing would ever tell it to stop.

Tracing a recursive call

It helps to trace through a small example by hand. Calling factorial_r(4) calls factorial_r(3), which calls factorial_r(2), which calls factorial_r(1), the base case, which returns 1 without calling itself again. That 1 is multiplied by 2 to give 2, which is multiplied by 3 to give 6, which is multiplied by 4 to give the final answer, 24. The calls go 'down' to the base case and then the multiplications happen 'back up' as each call returns.

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

sapply(0:8, fib)

• Recursion tends to read naturally for problems that are already defined in terms of smaller versions of themselves, such as factorials, Fibonacci numbers, or walking a nested list
• A loop can express the same idea for many simple cases and is often easier to reason about for straightforward counting or accumulating
• Naive recursive solutions, like the Fibonacci example above, can repeat the same calculation many times and become slow for larger inputs
• R limits how deeply functions can call themselves, so extremely deep recursion (tens of thousands of levels) can hit that limit

Recursion vs. iteration