We’ve studied functions factorial and fibonacci, which can be implemented either recursively or iteratively. In this section, we compare the two approaches and discuss why you might choose one approach over the other in a particular situation.
Both iteration and recursion are based on a control statement: Iteration uses an iteration statement (e.g., for or while), whereas recursion uses a selection statement (e.g., if or if…else or if…elif…else):
Both iteration and recursion involve iteration: Iteration explicitly uses an iteration statement, whereas recursion achieves iteration through repeated function calls.
Iteration and recursion each involve a termination test: Iteration terminates when the loop-continuation condition fails, whereas recursion terminates when a base case is reached.
Iteration with counter-controlled iteration and recursion both gradually approach termination: Iteration keeps modifying a counter until the counter assumes a value that makes the loop-continuation condition fail, whereas recursion keeps producing smaller 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, whereas infinite recursion occurs if the recursion step does not reduce the problem each time in a manner that converges on the base case, or if the base case is mistakenly not tested.
Recursion has many negatives. It repeatedly invokes the mechanism, and consequently the overhead, of function calls. This overhead can be expensive in terms of both processor time and memory space. Each recursive call causes another copy of the function (actually, only the function’s variables, stored in the stack frame) to be created—this set of copies can consume considerable memory space. Iteration avoids these repeated function calls and extra memory assignments. However, for some algorithms that are easily expressed and understood with recursion, iterative solutions are not readily apparent.