Wait, why use recursion when I can just use a for loop?

I get this question a lot. In most cases, a loop is more performant and easier to debug. But recursion shines when you're dealing with "branching" data—structures where you don't know how deep the nesting goes. Think of a file system with folders inside folders, or a deeply nested list in R where some elements are values and others are lists containing more lists.

If you try to use a for loop on a nested list, you have to decide ahead of time how many levels to go down. With recursion, the function just keeps diving until it hits a "base case." Here is a simple example where we want to sum all the numbers in a list, even if those numbers are buried inside other lists:

sum_nested <- function(x) {
  # Base case: if it's just a number, return it
  if (!is.list(x)) {
    return(x)
  }
  
  # Recursive step: sum the results of calling this function on each element
  sum(sapply(x, sum_nested))
}

my_list <- list(1, list(2, 3), list(list(4, 5), 6))
sum_nested(my_list) # Returns 21

See how sum_nested calls itself? It doesn't care if the list is two levels deep or twenty; it just keeps peeling the onion until it finds a number.

Why does my code crash with a "node stack overflow" after a while?

This is the "gotcha" of recursion. Every time a function calls itself, R doesn't just jump to the start of the function; it pushes a "frame" onto the call stack. This frame stores the current state, the local variables, and where the function needs to return to once the recursive call is finished.

The problem is that the stack has a finite size. If your recursion goes too deep—say, 5,000 calls—R will run out of room and throw a node stack overflow error. I've seen developers spend hours trying to fix their logic, only to realize the logic was fine, but the data was just too deep for the stack to handle.

You can check your current limit with options("expressions"). While you can increase it, doing so is usually a band-aid. If you're hitting the stack limit, it's usually a sign that you need a different approach.

Can tail recursion actually save me from the stack limit in R?

Here is the honest truth: not really. In languages like Haskell or Scheme, there is something called Tail Call Optimization (TCO). If the very last thing a function does is call itself (a "tail call"), the compiler replaces the current stack frame with the new one instead of adding a new one. This effectively turns the recursion into a loop under the hood, meaning it will never overflow the stack.

R, however, does not perform TCO. Even if you write your function in a "tail-recursive" style, R still pushes a new frame onto the stack.

So, what does a tail-recursive version look like? Instead of doing work after the recursive call (like the sum() in my first example), you pass the "running total" as an argument (an accumulator). Compare the two:

# Standard Recursion (Not tail-recursive)
factorial_standard <- function(n) {
  if (n == 0) return(1)
  return(n * factorial_standard(n - 1)) # Multiplication happens AFTER the call returns
}

# Tail Recursion (The recursive call is the very last action)
factorial_tail <- function(n, acc = 1) {
  if (n == 0) return(acc)
  return(factorial_tail(n - 1, n * acc)) # Nothing left to do but return the result
}

In a language with TCO, factorial_tail could run a million times without crashing. In R, both will eventually hit the stack limit. If you find yourself needing that kind of depth, I'd suggest switching to a while loop or using a package written in C++ via Rcpp.

📋 Practical Task

Exercise: Calculating the Total Depth of a Nested List Structure

Your task is to write a recursive function called get_max_depth. This function should take a list as input and return an integer representing the deepest level of nesting. For example, a flat list list(1, 2, 3) has a depth of 1, while list(1, list(2, list(3))) has a depth of 3.

• The function must handle cases where the list contains both atomic values (like numbers or strings) and other lists.
• If the input is not a list at all, the depth should be 0.
• Use sapply or a loop within your function to check the depth of each element and find the maximum.

Test your function with this object:

test_list <- list(
  "a" = 1, 
  "b" = list(2, 3), 
  "c" = list(list(list(4)))
)
# Expected output: 3