A linear recursive function calls itself at most once each time it is run.
To implement a linear recursive function:
- Test for base cases
- Begin by testing for a set of base cases (should be at least one).
- Every possible chain of recursive calls must eventually reach a base case, and the handling of each base case should not use recursion.
- Recur once
- Perform a single recursive call
- This step may have a test that decides which of several possible recursive calls to make, but it should ultimately make just one of these calls.
- Define each possible recursive call so that it makes progress towards a base case.