Рекурсия имеет собственное решение: т.е. система времени выполнения должна поддержать сложный стек вызовов, сверх необходимости выполнять обычные оценки в функции. Часто бывает выгодно заменить рекурсию итерацией, которая не требует у системы такого времени выполнения.
Например, следующая основанная на цикле факториал-функция выполняется быстрее и использует меньше памяти (в стеке вызовов) чем рекурсивная версия, представленная ранее.
| 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 |
Всегда (во всех случаях) можно заменять рекурсию, и лучшая замена это замена рекурсии циклами. Но следует помнить, в некоторых случаях, однако, рекурсия может быть превосходящим методом. Нерекурсивные версии определенных алгоритмов могут быть настолько сложными, что программировать их вызывает усиление не компенсируемые эффективностью, т.е. не стоят добавленного усилия.