# M09: Patterns of Recursion

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

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.