Linear Recursion: Factorial and Sum

Linear Recursion: each call generates at most one further call. Factorial: n! = 1 for n <= 1, otherwise n * (n-1)!. Sum 1..n is analogous.

The call depth is $\Theta(n)$. The work is $\Theta(n)$ if constant work is done per frame.

Iterative variants avoid stack growth and are often more robust in Java.

Linear recurrence as stairs: Climbing Stairs [1].

Where used

Teaching form for induction and for reading specifications. In production, linear chains are often replaced by loops; the recursive form remains visible in proofs, in functional languages, and in code generator output.

Depth

Linear recursion generates at most one further recursive call per activation. The number of active levels corresponds, in factorial or prefix sum computations, to the size of the input that has yet to be processed.

The factorial definition combines the smaller result upon returning with the current factor. A sum function over an array can similarly use the index or remaining length as a progress measure. Both require linear time and linear call storage.

Numerical limits remain independent of the recursion form. int and long overflow even with moderate factorial arguments; for exact large values, BigInteger is necessary.

Difficulty levels

1. Track the call and return phase of linear recursion.
2. Derive time and space requirements from the progress measure.
3. Separate recursion logic from numerical overflow.

Pitfalls

A correct termination does not protect against arithmetic overflow. Often, only the number of calls is considered, while the concurrently used call storage is forgotten.