CS 135 (Module 9: Patterns of Recursion)

In simple recursion, every argument in a recursive function application are either:

- Unchanged
- One step closer to a base case, using the inverse of the function in the data definition

Looking at indicators of the accumulative recursion pattern,

1. all arguments to recursive function applications are
- unchanged, or
- one step closer to a base case in the data definition, or
- a partial answer (passed in an accumulator)
2. The value in the accumulator are use in one or more base cases
3. The accumulatively recursive function usually has a wrapper function that sets the initial value of the accumulator

When does mutual recursion occur?

It occurs when two or more functions apply each other: f applies to g and g applies f

In simple recursion,

all arguments to the recursive function application (or applications, if there are more than one) are either unchanged, or one step closer to a base case in the data definition

In accumulative recursion,

parameters are as above, plus parameters containing partial answers used in the base case

In mutual recursion,

two or more functions call each other. Parameters usually behave as in simple recursion, but that is not required

In generative recursion,

parameters are freely calculated at each step.