Recursion — Functions that Call Themselves
The garden is laid out in beds, some beds are split into sections, and some sections into plots. Totalling a structure like that, where each part can contain smaller parts of the same shape, is awkward with loops and natural with recursion: a function that solves a problem by calling itself on a smaller piece of it.
The rule
Every recursive function needs a base case and a smaller step towards it.
- The base case is a version of the problem so small that the answer is obvious, so the function returns it directly.
- The recursive step handles one small piece itself and hands the rest to a call of the same function, on a smaller input.
total_kg <- function(x) {
if (length(x) == 0) return(0) # base case: nothing left to add
x[1] + total_kg(x[-1]) # first plot + total of the rest
}
total_kg(c(12.5, 8, 15, 3.5, 6)) # 45Each call peels off the first weight, so the input shrinks by one element every time and must eventually reach the empty vector, the base case.
The classic example is the factorial, where 5! means 5 × 4 × 3 × 2 × 1:
fact <- function(n) {
if (n <= 1) return(1) # base case
n * fact(n - 1) # smaller step
}
fact(5) # 120Where recursion earns its place is nested data: a list of beds, each a list of sections, each a list of plots. A recursive function says "if this is a plain number, return it; if it is a list, total each item with this same function and add the results", and it handles any depth without knowing it in advance.
Where it does not is plain vectors. sum(kg) beats total_kg(kg) in speed and clarity. Every call also takes up memory until it finishes, so very deep recursion (thousands of levels) stops with an error. Forget the base case, or make a step that does not shrink the input, and you hit that limit almost at once: the calls never end, so R stops them with an error once they nest too deeply.
The shortcut
Trust the smaller call. When writing, assume total_kg(x[-1]) already works for the rest, and only ask two questions: is the base case right, and does each step shrink the input? When tracing, write the calls going down, then complete the sums coming back up.
Going down
fact(4)needs4 * fact(3).
Drills
Answer fast — trust the rule.
What is fact(5)?
What does total_kg(numeric(0)) return?
How many times is total_kg called, in total, for a 5-element vector?
With fib <- function(n) if (n <= 2) 1 else fib(n - 1) + fib(n - 2), what is fib(6)?
What happens if you delete the base case line from fact?
Remember
- Every recursive function needs a base case and a smaller step towards it.
- Shortcut: trust the smaller call; trace down to the base case, then build the answer back up.
- Trap: a missing base case, and using recursion where
sum()or a loop is simpler.