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:

- Introduce “accumulative recursion” so you can begin to use it.
- 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

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

One more short video on why this is hard.

Video: Download 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.

## Commentary