Recursion comes with a price: the run time system has to maintain a complicated call stack, on top of having to perform the usual evaluations contained in the function. Often, we can eliminate recursion in favor of iteration, which does not make similar demands on the run-time system.
For example, the following loop-based factorial function is guaranteed to execute faster and consume less memory (in the call stack) than the recursive version presented earlier.
| 1: 2: 3: 4: 5: 6: 7: 8: | int factorial(int n) { int x = 1; for (int i = 2; i <= n; ++i) { x *= i; } return x; } |
| Listing 4Non-recursive factorial calculation |
It is always possible to eliminate recursion, and it is worthwhile to think about replacing recursion by loops. In some cases, however, recursion may well be the superior method. Non-recursive versions of certain algorithms may be so much more complicated to program that the gain in efficiency is not worth the added effort.