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.go 
package main

import "fmt"

func factorial(n int) int {
	if n == 0 {
		return 1
	}
	return n * factorial(n-1)
}

func main() {
	result := factorial(5)
	fmt.Println(result)
}

Complexity

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

Implementation notes

  • Go: same recursive shape as the other languages, with func factorial(n int) int documenting the integer contract.
  • 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)`