M09: Patterns of Recursion

Slides

Commentary

Towards the end of the last module we took a brief aside to discuss MergeSort. We said it’s not simple recursion. So what kind of recursion is it?

Turns out it’s “generative recursion” – one of the hardest kinds to work with.

The purpose of this module is two-fold:

  1. Introduce “accumulative recursion” so you can begin to use it.
  2. Help you recognize “generative recursion” so you can avoid it until we learn more about it.

To identify simple recursion, look at the arguments to the recursive function appliction – those places where the function applies itself recursively.

(define (func lst) ... (func (rest lst)) ...) ;; Simple
(define (func lst x) ... (func (rest lst) x) ...) ;; Simple
(define (func lst x) ... (func (process lst) x) ...) ;; NOT Simple
(define (func lst x) 
 ... (func (rest lst) (math-function x)) ...) ;; NOT Simple

Need a review of the signs of simple recursion? Follow the link.

Here is the implementation of max-list that we discussed in the M06 video on non-empty lists:

(define (max-list nums)
  (cond [(empty? (rest nums)) (first nums)]
        [else (max (first nums)
                   (max-list (rest nums)))]))

It uses the built-in function max to take the maximum of the first number on the list and the number returned by processing the rest of the list recursively. It uses simple recursion and works correctly.

The version on the slide might result from the following very reasonable thought process:

The application of any function, including max, requires some overhead. Since max is so simple I’ll just write the code in max-list to find the maximum of the two numbers without max and the associated overhead.

This is a commonly used optimization called “in-lining” (usually done by computer programs like DrRacket, not humans).

In this case “in-lining” fails, massively. Watch the video to see how and why.

Video: Download m09/m09.20_max-list

video m09/m09.20_max-list

You’ve already seen many of the functions in the examples column. We’ll see binary-search in M11 and quicksort in M15. mergesort (which you may have seen at the end of the previous module) is another example of O(n lg n).

We don’t expect you to do much with efficiency at this point. We want you to know that functions can be placed into different “families” of efficiency and that some of those families are considerably more efficient (faster) than others.

We do expect you to be able to recognize when your function applies itself recursively twice and to be able to avoid that. Note that the following code is not necessarily a problem:

(define (foo ...)
       ... (foo ...)   ;; application 1
       ... (foo ...)   ;; application 2
)

It’s OK if an application of (foo ...) applies foo at either application 1 or application 2. It’s a problem if one application of foo does both of them.

The note is important: humans usually employ a strategy that seems to be fast that is different from either of the two max-list strategies we’ve seen. Can we implement the “largest-element-seen-so-far” strategy in Racket?

max-list/acc is not simple recursion! In simple recursion the arguments where max-list/acc is applied would be either one step closer to the base case or unchanged. The first argument, (rest lon), is one step closer to the base case. But the second argument is sometimes max-so-far (that is, unchanged) and sometimes (first lon). It’s that last one that kills it. (first lon) is neither one step closer to the base case nor is it unchanged. Therefore this isn’t simple recursion.

max-list2 is a simple wrapper around max-list/acc, which does the actual work. Wrappers are often used with accumulative recursion due to the extra parameters which need to be initialized.

The first time max-list/acc is applied the max-so-far parameter is set to 1, the first element on the list. The lon parameter is set to the rest of the list.

That first application of max-list/acc looks at the first element of lon, the remainder of the list, and realizes that it’s bigger than the maximum value seen so far. So max-list/acc is applied with that new value (2) and the rest of the list. This happens 2 more times with 3 and 9. At each stage max-so-far is the maximum value seen in the list so far.

When the first value of lon is 5, it is not bigger than max-so-far and so max-so-far is left unchanged in the next function application.

When the list is empty we’ve examined the entire list and max-so-far is the answer produced by the base case.

Simple recursion will continue to be the main tool in our programming toolbox. However, sometimes accumulative recursion will be easier or yield a more efficient or elegant solution. In such cases we strongly encourage you to use it.

Just like there are indicators to identify simple recursion, there are indicators to identify accumulative recursion.

An accumulative function requires at least one accumulator; there may be more than one.

my-reverse uses simple recursion. It does not use the double application that got max-list into trouble but is still problematic. Watch this short video for the intuition of why that’s the case and why the revision on the next slide is much better.

Video: Download m09/m09.50_reverse

video m09/m09.50_reverse

One more short video on why this is hard.

Video: Download m09/m09.70_gcd

video m09/m09.70_gcd

“Freely calculated” means that there are no constraints. Simple recursion has the constraint that the calculation must give a result that’s one step closer to the base case. Accumulative recursion has a constraint that the calculation must be closer to the solution.

With generative recursion, there are no constraints on the calculations.

In CS135, if it’s not the simple recursion pattern and it’s not the accumulative recursion pattern, then it must be the generative recursion pattern.