Chapter 4
In a recursive subprogram,** the body of the subprogram contains a call to itself.**
Recursion is used when the original task can be reduced to a simpler version of itself. The idea
is that after a number of successive reductions, the reduced problem will eventually be simple
enough to be solved directly, and its solution will be used to piece together a solution to the
original problem.
Recursion can simplify the design of algorithms and the code, but requires more memory than loops.
- A recursive algorithm must have base case(s)
- It must call itself recursively
- It must change its state and move toward the base case
Terminal case: a case that contains no further calls to the recursive subprogram
**Trace diagram **
