Переписать рекурсивную функцию без использования рекурсии - PullRequest
Новая
       21

Переписать рекурсивную функцию без использования рекурсии

9 голосов
/ 12 декабря 2010

Я переписываю некоторый существующий код в настройках, где рекурсивные вызовы не так легко реализовать или не нужны. (И в Fortran 77, если вы должны знать.) Я думал о создании стека с нуля, чтобы отслеживать необходимые вызовы, но это кажется глупым, и я бы не стал выделять память для массива в случаях, когда рекурсия не глубокая (Я не уверен, что Fortran 77 также поддерживает динамический размер массива.)

Любые другие предложения для общего решения о том, как взять явно рекурсивную функцию и переписать ее не рекурсивно, не тратя место в стеке?

Большое спасибо, Старый Макст

Ответы [ 3 ]

15 голосов
/ 12 декабря 2010

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

function dosomething(a,b,c,d) 
{
  // manipulate a,b,c,d
  if (condition) 
    return dosomething(a,b,c,d) 
  else
    return something;
}

Into: 

function dosomething(a,b,c,d) 
{
  while (true) 
  {
    // manipulate a,b,c,d
    if (condition) continue;
    else return something;
  }
}

Без хвостовой рекурсии единственным решением является использование стека (или аналогичного промежуточного хранилища).

3 голосов
/ 12 декабря 2010

Классической рекурсивной функцией, которую можно записать в виде цикла, является функция Фибоначчи: 

 function fib(n)
 {
     // valid for n >= 0
     if (n < 2)
         return n;
     else
         return fib(n-1) + fib(n-2);
 }

Но без напоминания это требует O (exp ^ N) операций со стеком O (N).

Можно переписать: 

 function fib(n)
 {
     if (n < 2)
        return n;
     var a = 0, b = 1;
     while (n > 1)
     {
         var tmp = a;
         a = b;
         b = b + tmp;
         n = n - 1;
     }   
     return b;
 }

Но для этого нужно знать, как работает функция, и не уверен, что ее можно обобщить до автоматического процесса.

2 голосов
/ 12 декабря 2010

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

...