Шаблоны разработки для преобразования рекурсивных алгоритмов для повторяющихся

A common technique that I use where I'm on the process of replace a recursive algorithm by an iterative one is generally to use a stack, pushing the parameters that are being passed to the recursive function.

Check the following articles:

• Replacing Recursion With a Stack
• Stacks and Recursion Elimination (pdf)

Обычной практикой является управление стеком LIFO, в котором хранится текущий список того, что «еще предстоит сделать» , и обработка всего процесса в цикле while, который продолжается, пока список не станет пустым.
В этом шаблоне то, что было бы рекурсивным вызовом в истинной рекурсивной модели, заменяется на
- размещение «контекста» текущей (частично завершенной) задачи в стек,
- размещение новой задачи (той, которая вызвала рекурсию) в стек
- и для «продолжения» (т.е. перехода к началу) цикла while. Near the head of the loop, the logic pops the most recently inserted context, and starts work on this basis.

Effectively this merely "moves" information which would have otherwise been kept in nested stackframes on the "system" stack, to an application-managed stack container. It is an improvement however, for this stack container can be allocated anywhere (the recursion limit is typically tied to limits in the "system" stack). Therefore essentially the same work gets done, but the explicit management of a "stack" allows this to take place within a single loop construct rather than recursive calls.

Часто общую рекурсию можно заменить хвостовой рекурсией, собирая частичные результаты в аккумулятор и передать его рекурсивным вызовом. Хвостовая рекурсия по существу итеративна, рекурсивный вызов может быть реализован как переход.

Например, стандартное общее рекурсивное определение факториала

factorial(n) = if n = 0 then 1 else n * factorial(n - 1)

может быть заменено на

 factorial(n) = f_iter(n, 1)

и

 f_iter(n, a) = if n = 0 then a else f_iter(n - 1, n * a)

, которое является хвостовым рекурсивным. Это то же самое, что

a = 1;
while (n != 0) {
    a = n * a;
    n = n - 1;
}
return a;

Have a look at these links for performance examples

Recursion VS Iteration (Looping) : Speed & Memory Comparison

and

Replace Recursion with Iteration

and

Recursion vs Iteration

Q: Is the recursive version usually faster? A: No -- it's usually slower (due to the overhead of maintaining the stack)

 Q: Does the recursive version usually use less memory?
 A: No -- it usually uses more memory (for the stack).

 Q: Then why use recursion??
 A: Sometimes it is much simpler to write the recursive version (but

we'll need to wait until we've discussed trees to see really good примеры ...)

Обычно я начинаю с базового случая (каждая рекурсивная функция имеет один) и работаю в обратном направлении, при необходимости сохраняя результаты в кеше (массиве или хеш-таблице).

Ваша рекурсивная функция решает проблему, решая более мелкие подзадачи и используя их для решения более крупного экземпляра проблемы. Каждая подзадача также разбивается дальше и так далее, пока подзадача не станет настолько маленькой, что решение станет тривиальным (т.е. базовый случай).

Идея состоит в том, чтобы начать с базового случая (или базовых случаев) и использовать его для построения решение для более крупных случаев, а затем использовать их для создания еще более крупных случаев и так далее, пока не будет решена вся проблема. Это не требует стека и может быть выполнено с помощью циклов.

Простой пример (на Python):

#recursive version
def fib(n):
     if n==0 or n==1:
             return n
     else:
             return fib(n-1)+fib(n-2)

#iterative version
def fib2(n):
     if n==0 or n==1:
             return n
     prev1,prev2=0,1 # start from the base case
     for i in xrange(n):
             cur=prev1+prev2 #build the solution for the next case using the previous solutions
             prev1,prev2=cur,prev1
     return cur

Один из шаблонов - Хвостовая рекурсия :

Вызов функции называется хвостовым рекурсивный, если нечего делать после возврата из функции, кроме вернуть его значение.

Wiki .