Chapter 11 (pp. 203–210) of Computer Science I.

Topics

Key Ideas

• Every recursion needs a base case and progress toward it.
• Tail recursion — the recursive call is the last action; can be optimized to iteration.
• Memoization — cache results to avoid recomputation (e.g. Fibonacci).
• Coverage is intentionally shallow at CS1 level. Recapitulated briefly in each language part (C, Java, PHP).

Examples

Factorial (base case + recursive case)

function factorial(n):
  if n ≤ 1:              // base case
    return 1
  return n × factorial(n - 1)

Fibonacci with memoization

memo ← empty map
function fib(n):
  if n < 2: return n
  if n in memo: return memo[n]
  memo[n] ← fib(n - 1) + fib(n - 2)
  return memo[n]

Caching turns exponential work into linear.

In Java

static long factorial(int n) {
    if (n <= 1) return 1;               // base case
    return n * factorial(n - 1);
}

static Map<Integer, Long> memo = new HashMap<>();
static long fib(int n) {
    if (n < 2) return n;
    if (memo.containsKey(n)) return memo.get(n);
    long v = fib(n - 1) + fib(n - 2);
    memo.put(n, v);
    return v;
}

Citations

[1] Computer Science I, Ch. 11, pp. 203–210.