Computer Algorithms II Lecture Notes

20 September 2007 • Recursion In Practice

Outline

• Recursion, advantages and disadvantages.

• Recursion examples.

• Implementation and costs.

• Automatic and maunal optimizations.

Recursion

• The general recursive framework is

  1. Split a problem into smaller similar, subproblems.

  2. Repeat until the subproblems are trivial.

  3. Recombine subproblem solutions into a solution for the originating (sub)problem.

• The framework is driven by the problem structure, either naturally or induced.

Recursion Advantages

• Recursion's advantages include:

  • Simplicity: the trivial problem, dividing problems and recombining solutions.

  • Wide applicability: recursion can be discovered in surprising places.

  • Transparency: correct recursive algorithms are correct (almost) by inspection.

  • Cliched: recursion works unmodified over a wide range of problems.

Recursion Disadvantages

• Problems with recursion include

  • Computational expense.

    • Easily and (usually) automatically transformed into more efficient forms.

  • Opacity, particularly among the uninitiated.

    • Oh well.

  • Subtle design errors.

    • Few hiding places.

Iterative Matrix Sum

• Given two n × n matrices, return their sum.

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

• Simple and fast.

Recursive Matrix Sum

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)

• What's the recursive matrix structure used?

Matrix Decomposition

• A matrix is a row on top of a matrix, but what is a row?

  • This decomposition is degenerate.

• Is there a non-degenrate decomposition?

Another Matrix Decomposition

• Represent (sub-)matrices by their upper-left corner and size: x, y, n.

Another Matrix Recursion

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')

• This code assumes n = 2ⁱ, i ≥ 0.

  • The general case is similar but messier.

Which is Better?

• Which is better: row-by-row and col-by-col or matrix-sum?

• It depends:

  • 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.

• In general, matrix-sum loses. Why?

Does It?

	C++, sec/sum
Method	-O0	-O3
loop	0.71	0.27
2-recursive	0.66	0.24
1-recursive	1.50	1.10

• 1024×1024 matrices, average of ten sums, standard deviations from 300 to 20,000 μsec.

• 1.6 GHz cpu, Debian testing, g++ 4.1.3.

• See the C++ code.

Recursion's Cost

• Why is recursion expensive at runtime?

  Recursion

  • Creates a bunch of subproblems.

  • Solves each of the subproblems.

• Recursion's cost comes from creating and then solving a bunch of subproblems.

  • Each activity has a run-time cost not incurred by the equivalent non-recursive code .

Implementing Recursion

• An recursion implementation has to deal with all those subproblems.

  • Storing them and executing them.

• A limitation: only one executing (sub)problem per program (single-threaded execution).

  • Multiple executing (sub)problems are restricted to a small (≤ 64) total amount.

• Use the only tool we have: subroutines.

  • That's execution. What about storage?

Activation Records

int f() int i, j double x // whatever	Given a function with local variables, where are the local variables stored?
	In a storage block called the activation record. But where are the activation records stored?

Activation Stack

• Procedures return in reverse calling order.

  a() a() calls b() b() calls c() c() returns b() returns a() returns

• Use a stack, the activation (or run-time) stack.

Recursion's Cost

• The cost of recursion is the cost of the subroutines.

  • Executing the call and handling the storage.

• Calling is heavily optimized at the system and architecture level.

  • But however cheap a call may be, not making a call is cheaper.

• Tail-call recursion can optimize the calls away.

Tail Calls

• A tail call a subroutine call made just before procedure exit.

  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

• A recursive tail call can be replaced by a branch to the subroutine start.

• This is known as tail-call optimization.

  • The result is a loop.

Example.

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)

• col-by-col can be tail-call optimized into a loop.

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

Example..

row-by-row(row, n)
  if row < n
    col-by-col(row, 0, n)
    row-by-row(row + 1, n)

• In-line replace col-by-col with the loop

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

Example...

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

• Tail-call optimize row-by-row.

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

Tail-Call Problems

• Not all recursion can be cast into tail-call form.

  • The regularly recursive matrix-sum().

• Sometimes casting recursion in tail-call form makes it more complex.

  • Compare row-by-row() and col-by-col() with matrix-sum().

• Unsuccessful tail-call optimizations leave recursive calls.

Explicit Storage Management

• When tail-call optimization fails, the recursion has to be manually removed.

• This involves (usually) an explicit loop over stored subproblems.

• Example: print the reverse of a singly-linked list.

  rprint(link)
    if link ≠ nil
      rprint(link→next)
      print(link→data)
  

Example

• Recursion relies on procedure calls, procedure calls rely on the run-time stack.

  • Use a stack as the intermediate storage.

  rprint'(link)
  
    for l = link; l ≠ nil; l = l→next
      stack.push(l)
  
    while not stack.empty()
      print stack.pop()→data
  

• Any data structure will do, as long as it preserves the proper order.

References

• Debunking the “Expensive Procedure Call” Myth (or Lambda: The Ultimate Goto) by Guy Steel, AI Memo 443, MIT, 1977.

• Considering Recursion by Arch Robison in Dr. Dobb's Journal, March 2000.