Version 4.1.3¹

Handouts: TailRecursion.hs, quicksort.hs, mergesort.hs, fibonacci.hs

9.1 Thinking Recursively

• Towers of Hanoi. Again. First time I've seen it as a game.

• Developing the recursive solution, starting small:

  • Solution for N = 1
  • Solution for N = 2—Hey, this uses the N = 1 solution!
  • Solution for N = 3—Hey, this uses the N = 2 solution!
  • …
  • And in general—Hey! the solution for N uses the solution for N − 1.

• Recursion:

  1. Base case: a form of the problem that is so simple it can be solved directly and simply.
  2. Recursive case (or step): a form of the problem that is more complex; it can be solved (in part) by solving a smaller problem of the same kind.

• Second example: printing a linked list backwards.

  • The recursive solution is more efficient! (Θ(N) vs. Θ(N²))

• Demonstrating that a recursive method is correct (p. 230):

  • Show that the base case is correct.
  • Show that if correct for N − 1, then it's correct for N. (Or in general it might be N − 2 or N / 2 instead of N − 1; the point is, if it's correct for a certain smaller case than N, then it's correct for size N).
  • Example: see power in TailRecursion.hs

9.2 Analyzing

• Recurrence relations:

  T(N) = T_a if base case;

  T(N) = T_b otherwise.

• The recurrence relation is a recursive formula (say, for running time). Solving the recurrence relation means putting it into closed (non-recursive) form.
• Example: Towers of Hanoi, recurrence relation, and solution….
• In general, this is not easy. Often we must guess at the solution and try to verify our guess. Usually, verifying a correct guess is relatively simple, though.
• It can be helpful to draw the "recursion tree" (p. 233), especially if it's branchy, but also if not.

• Typographical error on p. 234: Θ(2n) should be Θ(2ⁿ)

9.4 Quicksort

• The idea:
  • Pick an element p as the pivot element (textbook: the last element)
  • Partition the array into [x: x ≤ p], [p], [x: x > p]
  • Recursively, quicksort the two sub-arrays left and right of p.
• A "cute" Haskell implementation or two
  • quicksort.hs
  • Illustrates the idea very clearly
  • But is not efficient because it does not sort "in place"
• The strategy: another divide and conquer.
• The code:
  • quicksort
  • quicksortHelper
  • partition
    • Works by maintaining four regions in the array: [ ≤pivot ] [ >pivot ] [ unclassified ] [ the pivot element ]; the first two regions expand as the third shrinks to nothing.
    • Method:
      1. Choose A[N-1] as pivot p.
      2. Traverse the array: for each element x before p:
         1. If x > p, leave it in place.
         2. If x ≤ p, swap it with the first (lowest-indexed) element of the (>p) region.
      3. At the end, swap p with the first (lowest-indexed) element of the (>p) region. Consequently at the end we have: [ ≤pivot ], [ pivot ], [ >pivot ].
• Analysis:

  • The recurrence relation: assuming that partitioning an array of size N divides it into two nearly equal-sized parts (approximately N/2 each):

    T(N) = 1, if N = 1;

    T(N) = N + T(N/2) + T(N/2 − 1), otherwise.

  • Its solution (compare to merge sort) is Θ(N log N).
  • Unfortunately, the assumption that partitioning leads to two nearly equal-size sub-arrays is not always valid.
    • If the array is in ascending order, partitioning an array of N elements produces sub-arrays of size 0 and N − 1. The worst-case running time for quicksort is therefore Θ(N²).
    • Compare to insertion sort!

• Modifying the algorithm to pivot on a randomly selected element, instead of the last element.

• Quick-sort with Hungarian folk dance (YouTube, 6:55)

9.3 Merge Sort

• The idea:
  • If the array has one element or less, we are done.
  • Otherwise, divide the array into two parts at the middle. Recursively merge-sort each half. Then merge the two halves.
• The strategy: divide and conquer.
• Merge takes two sorted lists and forms a sorted list from all their elements. It works by repeatedly taking the smaller number from the front of each list.
• Coding it:
  • Haskell: mergesort.hs
    • In this case, it is a seriously efficient function, not a "toy" implementation.
  • Java: …
• Analysis:

  • The recurrence relation:

    T(N) = 1, if N = 1;

    T(N) = N + 2 T(N/2), otherwise.

  • Compare quicksort.

  • Its solution: T(N) = N (1 + log₂ N), which is in Θ(N log N).

• Merge-sort with Transylvanian-Saxon dance (YouTube, 4:16)

9.5 Avoiding (Why? When?) Recursion

• Equivalence of iteration and recursion: any problem which can be solved iteratively, can also be solved recursively, and vice-versa.
• So which is better?
  • The recursive method is sometimes more elegant, but less efficient.
  • The inefficiency comes from the operations on the stack used to implement recursive method calls.
  • Tail recursion (where the recursive call is the last action of the function) can be easily converted to iteration, since the callee does not have to remember to come back and perform any remaining operations in the caller.
    • Example: see powerTR, powerTRloop in TailRecursion.hs
    • Compilers for functional languages (Scheme, Haskell, etc.) will (usually) do this automatically.
    • Java programmers are not so lucky.
  • Non-tail recursive methods are less easily converted to iterative forms, typically by using an explicit stack to "simulate" the recursion. Consequently, not much gain.

  • What the author does not say:

    Don't optimize code prematurely and unnecessarily. While it is true that in many programming languages, recursive functions or methods are less efficient than iterative ones, and functional operations may be even less efficient, we always should remember that clarity is usually more important than efficiency except in time-critical sections of code.

  • A particularly nasty example: the "natural recursive" algorithm (or should we say the naive recursive algorithm?) for the Fibonacci function has exponential running time. The "dynamic programming" variant uses an array to keep track of the previous Fibonacci values, and has running time Θ(N).
    • This is not an iterative form of the recursive algorithm; it is an altogether different algorithm!

    • However, we can do better than this. The array uses Θ(N) space, but we only use the two most recently set elements. These can be represented by just two int variables. This can be done iteratively:

      def fibn (n):
        a = 1 // fib(0), will store fibn(j - 2) in the loop
        b = 1 // fib(1), will store fibn(j - 1)
        loop for j = 2 to n:
          c = a + b // = fibn(j)
          a = b
          b = c
        end loop  // so now j == n
        return c

      or recursively:

      def fibr (n):
        if n < 2:
          return 1
        else
          // fib(0) = 1, fib(1) = 1, fib(2) is next
          return fibrr (1, 1, 2, n)
      
      def fibrr (a, b, i, n):
        c = a + b // = fib(i)
        if i == n:
          return c
        else
          return fibrr (b, c, i + 1, n)

    • Haskell (both versions): fibonacci.hs

Exercises

• Page 231: 9.3 palindrome, 9.4 recursive binary search
• Pages 234–5: 9.7?
• Pages 243–4: 9.3? (9.15 assigned as homework)

Footnotes