Data Structures and Algorithms Lecture Notes

31 January 2011 • Recursion

---

Outline

Some problems. Structural, inductive, and degenerate recursion. Use and abuse. Advantages and disadvantages. Examples Implementation and costs.

A Boxy Picture

• How do you draw this picture?

Investments

• Every year you can invest in a stock, or
  every two years you can invest in a bond.
  • The same amount is invested every year.
  • One active investment at any time.

    

• The expected return in year y is S(y) for the stock and B(y) for the bond.
• Based on expected returns, what investment strategy maximizes return over n years?

Choices

• Given { 1, 2, 3, 4 } (n = 4), how many ways are there to choose 2 numbers?

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

  • Six, apparently.
• Given n distinct items, how many ways are there to pick i ≤ n items?

Finding Max Sum Paths

• Find the neighbor triangles’ max sum paths.
• Pick the neighbor with the larger max sum path.

Recursion

• General approach:
  1. Split a problem into smaller similar, subproblems.
  2. Repeat until the subproblems are trivial.
     • “Trivial” means solved with no computation.
  3. Recombine subproblem solutions into a solution for the originating (sub)problem.
• This approach is called recursion.

Recursion Format

• The trivial subcomputation in step 2 is called the base case.
• The recursive steps 1 and 3
  • Simplifies a problem into smaller similar subproblems.
  • Recursively applies the algorithm to the subproblems.
  • Combines the subproblem solutions into a more complete solution.

Recursion Advantages

• The advantages of exploiting recursion 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: the same damn thing over and over.

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.

Finding Recursion

• Recursion relates directly to the problem’s structure.
• There are three general recursion sources:
  1. The problem or data structure; structural recursion.
  2. Linear structures; inductive recursion, a special case of structural recursion.
  3. optimized (usually) semi-recursive algorithms; degenerate recursion.

Structural Recursion

• Structural recursion is (almost) a gimme; it follows from the problem or data structure.
  • Although the problem or data structure may not be the best one to use.
• Examples:
  • The max sum path problem: a triangle is an apex with left and right subtriangles.
  • Trees: a tree is a node with a set of trees as children.

Recursive Data Structures

• A recursive data structure D is defined by
  • A base case giving the simplest possible instance of D.
  • A constructive case that combines one or more D instances and other data into a new, single D instance.
• A recursive algorithm undoes the structure created by the constructive case.
  • And stops recursing at the base case.

Example

• An n-ary tree of type T is
  • Nothing (the base case).
  • A value of type T and up to n n-ary trees of type T.

  A recursive algorithm:

  bool find(v, root) if root == nil return false if root.value == v return true return find(v, root[0]) || ... find(v, root[n-1])

Inductive Recursion

• Inductive Recursion is structural recursion over linear structures.
  • Arrays, sequences, and the like.
• The subdivision is usually (but not always) into a single element and the rest of the structure.
• With care, inductive recursion can be automatically transformed into efficient looping code (tail-call optimization).

Example

• Find an element x in an array.
• Base case: finding an element in an empty array is trivial.
• Recursive case:
  • Splint an n-element array into a 1-element array and an array with n - 1 elements.
  • If x is in the 1-element array, return true.
  • Otherwise, return the result of recursing on the array with n - 1 elements.

Example Code

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()])

Degenerate Recursion

• Sometimes extra information can be used to modify the recursive structure to produce a better design.
  • But possibly not producing something following the typical recursive pattern.
• Example: searching for x in an unordered array vs. an ordered array.

Unordered Array Searching

• No extra knowledge about an unordered array; use straight inductive recursion.

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

Ordered Array Searching

• The extra ordering information helps eliminate the subproblems.

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

Recursion Requirements

• To use recursion successfully, should have
  • A base case (a trivial subproblem).
  • A way to divide the problem into subproblems.
  • A way to combine subproblem solutions.

Recursive Design

• Make sure the base case is
  • Really a base case (that is, a trivial instance of the problem).
  • Is correctly solved.
• Make sure the recursive step
  • Creates subproblems related into the original problem.
  • Combines subproblem solutions into a solution for the larger problem.

Recursion Pitfalls

• Although it’s simple, it’s possible to get recursion wrong.
  • The base case is wrong, incomplete, or incorrectly solved.
  • The subproblems are incorrectly derived from the original problem.
  • Subproblem solutions are incorrectly combined into an invalid solution for the original problem.

Wrong Base Cases

• The base case for factorial is 0, not 1.

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

Incomplete Base Cases

• How many 3- and 5-cent stamps equal any amount over 7 cents?
  • For example, 11 cents equals one 5-cent and two 3-cent stamps.
• The recursion seems easy:
  • The base case is 8 = 3 + 5.
  • For any value n > 7, n = n' + 3.
  • One more 3-cent stamp than needed for n'.

Stamp Counting Code

• That seems easy enough; here’s the code.

  int-pair stamps(n)
    if n == 8
      return (1, 1)
    return (1, 0) + stamps(n - 3)
  

• Unfortunately, this code is wrong. Why?

Revised Code

• There are three base cases:

  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)
  

Bad Subdivisions

• The subproblems must be strictly smaller than the original problem.
  • If not, the recursion won’t terminate.
• The subproblems must be really related to original problem.
  • Otherwise the subproblem solutions won’t be related to the original problem’s solution.

Quicksort

• Quicksort partitioning is slightly tricky code; getting it wrong breaks quicksort.

Improper Combinations

• Incorrectly combining correct subproblem solutions may lead to an incorrect original-problem solution.
• Given a set of planer points, find a pair with minimal distance between them.

  

Closest Points

• Repeatedly divide the point set in half until each piece contains at most two points.

  For two points, return the points; otherwise return nothing. From each half select the closest pair and return the smaller of the two pairs.

• Unfortunately, this doesn’t work. Why?

Dividing Closest Points

• A closest pair of points may exist between divisions of the point set.

  

• Correctly recombining subproblem solutions requires more work than just comparing the subproblem solutions.

Extended Example

• Matrix addition.
• Recursion’s cost.
• Reducing recursion’s cost.
  • Automatically.
  • By hand.

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.

Matrix Decomposition

• A matrix is a row on top of a matrix, but what is a row?
  • This decomposition is iterative.

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)

• Is there a non-iterative 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.

Does It?

	C++, sec/sum
Method	-O0	-O3
loop	0.71	0.27
iterative	0.66	0.24
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.
• In general, matrix-sum loses. Why?

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.

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.
• Gödel, Escher, Bach by Douglas Hofstadter, Basic Books, 1979.

Credits

pain in black - philip glass version by Feuillu under a Creative Commons BY NC License.

---

This page last modified on 28 August 2008.