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.scala 
object Main {
	def factorial(n: Int): Int = {
		if (n == 0) {
			return 1
		}
		n * factorial(n - 1)
	}

	def main(args: Array[String]): Unit = {
		val result = factorial(5)
		println(result)
	}
}

Complexity

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

Implementation notes

  • Scala: same recursive shape as the other languages, with def 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 `n * factorial(n - 1)`