6.21. Recursion vs. Iteration

This section compares the recursive and iterative problem-solving approaches and discusses why you might choose one over the other in a particular situation.

• Both iteration and recursion are based on a control statement: Iteration uses a repetition structure; recursion uses a selection structure.

• Both iteration and recursion involve repetition: Iteration explicitly uses a repetition structure; recursion achieves repetition through repeated function calls.

• Iteration and recursion each involve a termination test: Iteration terminates when the loop-continuation condition fails; recursion terminates when a base case is recognized.

• Iteration with counter-controlled repetition and recursion each gradually approach termination: Iteration modifies a counter until the counter assumes a value that makes the loop-continuation condition fail; recursion produces simpler versions of the original problem until the base case is reached.

• Both iteration and recursion can occur infinitely: An infinite loop occurs with iteration if the loop-continuation test never becomes false; infinite recursion occurs if the recursion step does not reduce the problem during each recursive call in a manner that converges on the base case.