Recursion and Dynamic Programming

Factorial (Recursive)

factorial(0) = 1, otherwise factorial(n) = n * factorial(n - 1). The smallest example of recursion with a single base case.

Algorithm

Canonical input n <- 5 descends through six call frames and unwinds through five multiplications. Final result 120.

Basic Implementation

basic.R 
factorial <- function(n) {
	if (n == 0) {
		return(1)
	}
	return(n * factorial(n - 1))
}

result <- factorial(5)
cat(result, "\n", sep = "")

Complexity

  • Time: O(n)
  • Space: O(n) call stack

Implementation notes

  • R: same recursive shape as the other languages, with factorial <- function(n) documenting the integer contract. R ships its own factorial() in base R as a vectorised wrapper around gamma(n + 1), which would hide the recursion the lesson teaches.
  • The replay treats the call stack as a vertical list of frames; descent pushes, unwind pops with the computed multiplication shown.
base case `if (n == 0) { return(1) }`
recursive call `return(n * factorial(n - 1))`