# M09: Patterns of Recursion

Hint: If possible, make your browser wide enough to place the slides and commentary side-by-side.

The slides on this page are not accessible (for screen readers, etc). The 1up and 3up slides are better.

## Module Topics

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?

It’s what we will call “generative recursion” – one of the hardest kinds to work with.

The purpose of this module is two-fold:

- Introduce “accumulative recursion” so you can begin to use it.
- Help you recognize “mutual recursion” and “generative recursion” so you can avoid them until we learn more.

To identify simple recursion, look at the arguments to the recursive function application – 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-v1 nums)
(cond [(empty? (rest nums)) (first nums)]
[else (max (first nums)
(max-list-v1 (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`max-list`

using`>`

to find the maximum of the two numbers without`max`

function 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.20_max-list

You’ve already seen many of the functions in the examples column. We’ll see `binary-search`

in M11.
`mergesort`

(which you may have seen at the end of the previous module)
is another example of O(n log_{2} 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 lst ...)
... (foo (rest lst) ...) ;; application 1
... (foo (rest lst) ...) ;; application 2
)
```

It’s OK if one 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.

In many cases the slow version does the exact same computation twice:
`(max-list-v2 (rest lon))`

. That leads to exponential blowup.

The fast version does the computation (`max-list-v1 (rest lon))`

and passes
that result to a helper function. The helper function can make use of that
value as often as it needs to without calculating it again, thus avoiding
exponential blowup.

This is a useful technique. We’ll see it again.

`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-list-v3`

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.50_reverse

This implementation of `my-reverse`

is a wrapper function that makes
use a `my-rev/acc`

, a helper function that does all of the real work
with accumulative recursion.

You can use this code to verify that you are getting the correct answers for reasonably small values of `n`

.

```
;; (fib n) Produce the n-th value in the Fibonacci sequence.
;; fib: Nat -> Nat
(define (fib n)
(cond [(< n 2) n]
[else (+ (fib (- n 1)) (fib (- n 2)))]))
```

We’ll often use mutual recursion when we write functions on general trees in M13.

This drawing by MC Escher illustrates mutual recursion well. Instead of “`f`

applies `g`

and `g`

applies `f`

”, we have “right hand draws left hand and left hand
draws right hand”.

One more short video on why this is hard.

Video: Download 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, we have fairly specific criteria for simple recursion, accumulative recursion, and mutual recursion. If the algorithm is recursive and not one of those three patterns, then it must be the generative recursion pattern.