R Recursion
Recursion is a pattern where a function calls itself. Each call works on a smaller part of the same problem.
Factorial with a base case
factorial gives back 1 for a value of 1 or less. A larger value multiplies itself by the factorial of one less.
factorial <- function(n) {
if (n <= 1) {
return(1)
}
return(n * factorial(n - 1))
}
print(factorial(5))
print(factorial(1))Add a vector from the front
sum_values adds the first value to the sum of the rest. An empty vector is the base case and gives back 0.
sum_values <- function(values) {
if (length(values) == 0) {
return(0)
}
return(values[1] + sum_values(values[-1]))
}
print(sum_values(c(10, 20, 30)))
print(sum_values(c(5)))
print(sum_values(c()))Build a countdown
count_down puts its value in front of the countdown for one less. The prints show the values in falling order.
count_down <- function(n) {
if (n < 1) {
return(c())
}
return(c(n, count_down(n - 1)))
}
print(count_down(3))
print(count_down(1))Example
factorial <- function(n) {
if (n <= 1) {
return(1)
}
return(n * factorial(n - 1))
}
sum_values <- function(values) {
if (length(values) == 0) {
return(0)
}
return(values[1] + sum_values(values[-1]))
}
print(factorial(4))
print(sum_values(c(3, 4, 5)))Key points
- A base case is a stopping rule that gives back a value directly.
- Without a base case, the calls never end and no result comes back.
- A recursive function calls itself inside its own block.
- Each call passes a smaller value than the call before it.
- The smaller values move the work towards the base case.
- The results combine as each call gives its value back to the call before it.
In this example factorial works on 4 and gives back 24. sum_values adds 3, 4 and 5 and gives back 12. Both functions call themselves with smaller values until a base case stops the chain.
Try it Yourself
Edit the code, then press Run.
Running is simulated · rdrr.io R Snippets
Exercise
What does the base case do in a recursive function?