| 
 |   | 


1, 2 2, 3 3, 4 1, 3 2, 4 1, 4 

|  | 
 | 
bool find(x, a[])
  if a.size == 0
    return false
  else 
    if a[0] == x
      return true;
    else
      return find(x, a[1..a.size()])
bool find(x, a[])
  if a.size == 0
    return false
  n = a.size/2
  if a[n] == x
    return true
  return find(x, a[0..n - 1]) || 
         find(x, a[n + 1..a.size])
bool find(x, a[])
  if a.size == 0
    return false
  n = a.size/2
  if a[n] == x
    return true
  if a[n] < x
    return find(x, a[n + 1..a.size])
  else
    return find(x, a[0..n - 1])
intfactorial(n) if n == 1 return 1 return n*factorial(n - 1) int factorial(n) if n == 0 return 1 return n*factorial(n - 1)
int-pair stamps(n)
  if n == 8
    return (1, 1)
  return (1, 0) + stamps(n - 3)
8 = one 3¢ stamp + one 5¢ stamp.
9 = three 3¢ stamps + no 5¢ stamps.
10 = no 3¢ stamps + two 5¢ stamps.
int-pair stamps(n)
  if n == 8
    return (1, 1)
  if n == 9
    return (3, 0)
  if n == 10
    return (0, 2)
  return (1, 0) + stamps(n - 3)


| 
 
 | 
 | 

for row = 1 to n
  for col = 1 to n
    s[row, col] = 
      a[row, col] + b[row, col] 

row-by-row(row, n)
  if row < n
    col-by-col(row, 0, n)
    row-by-row(row + 1, n)
col-by-col(row, col, n)
  if col < n
    s[row, col] = 
      a[row, col] + b[row + col]
    col-by-col(row, col + 1, n)
row-by-row(0, n)

matrix-sum(a[], b[], x, y, n)
  if n = 1
    s[x, y] = a[x, y] + b[x, y]
  else
    n' = n/2
    matrix-sum(x, y, n')
    matrix-sum(x + n', y, n')
    matrix-sum(x, y + n', n')
    matrix-sum(x + n', y + n', n')
row-by-row and col-by-col or
  matrix-sum?
  row-by-row and col-by-col is complex but potentially as
    efficient as the nested-loop code.
    matrix-sum is less complex but unlikely to be as efficient.
    | C++, sec/sum | ||
|---|---|---|
| Method | -O0 | -O3 | 
| loop | 0.71 | 0.27 | 
| iterative | 0.66 | 0.24 | 
| recursive | 1.50 | 1.10 | 
matrix-sum loses. Why?
  Recursion
- Creates a bunch of subproblems.
- Solves each of the subproblems.
| int f() int i, j double x // whatever 
 | 
 | 
| 
 
 | 
 | 
| 
 | 
 
 | 
row-by-row(row, n)
  if row < n
    col-by-col(row, 0, n)  // not a tail call
    row-by-row(row + 1, n) // a tail call
matrix-sum(). 
    row-by-row() and col-by-col() with matrix-sum(). 
    rprint(link) if link ≠ nil rprint(link→next) print(link→data)
rprint'(link) for l = link; l ≠ nil; l = l→next stack.push(l) while not stack.empty() print stack.pop()→data
| This page last modified on 28 August 2008. |