The Three Laws of Recursion¶

Like the robots of Asimov, all recursive algorithms must obey three important laws:

1. A recursive algorithm must call itself, recursively.
2. A recursive algorithm must have a base case.
3. A recursive algorithm must change its state and move toward the base case.

A base case is the condition that allows the algorithm to stop recursing.

• A base case is typically a problem that is small enough to solve directly.
• In the factorial algorithm the base case is n=1.

We must arrange for a change of state that moves the algorithm toward the base case.

• A change of state means that some data that the algorithm is using is modified.
• Usually the data that represents our problem gets smaller in some way.
• In the factorial n decreases.