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

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

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

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


recursion algorithm non-recursive rewrite
person Old McStopher    schedule 12.12.2010    source источник
comment
Если он не разветвляется, вы обычно можете переписать его в простой цикл. Если он разветвляется, вам обычно нужен стек   -  person CodesInChaos    schedule 12.12.2010
comment
@CodeInChaos: рекурсивная функция, которая не имеет ветвления, по определению никогда не вернется...   -  person Victor Nicollet    schedule 12.12.2010
comment
Думаю, я неправильно употребил слово "ветка". Я имею в виду вызовы самого себя несколько раз, поэтому граф вызовов становится деревом с ветвями. И это только мой опыт и не всегда правда.   -  person CodesInChaos    schedule 12.12.2010

Ответы (3)


arrow_upward
16
arrow_downward

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

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

В:

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

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

person Victor Nicollet    schedule 12.12.2010
comment
Это похоже на то, о чем я думал, но не мог выразить словами. Итак, в моем конкретном случае у меня есть набор данных элементов, каждый из которых нужно будет проверить на связь с другими элементами в наборе. Я мог бы передать структуру данных всех элементов, но, поскольку каждый из них требует дальнейшей обработки, я полагаю, что стек неизбежен, да? - person Old McStopher; 12.12.2010
comment
Зависит от. Если код предназначен в основном для всех пар (a, b), если P (a, b) истинно, тогда выполните F (a, b), вы можете избежать итеративного перебора всех пар... - person Victor Nicollet; 12.12.2010

arrow_upward
3
arrow_downward

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

 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;
 }

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

person Jason S    schedule 12.12.2010

arrow_upward
2
arrow_downward

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

person Ofir    schedule 12.12.2010
comment
Хотите показать рекурсивную функцию, не требующую места в стеке? Даже для своих аргументов? - person Nikita Rybak; 12.12.2010
comment
@Nikita Rybak: встроенная функция хвостовой рекурсии;) - person Victor Nicollet; 12.12.2010
comment
@Victor Да, но это в переписанном виде. А Офир утверждает, что существует рекурсивная функция, не требующая стековой памяти. Итак, мне любопытно. - person Nikita Rybak; 12.12.2010
comment
@Jason Вы говорите, что ваша рекурсивная функция не зависит от такого хранилища? - person Nikita Rybak; 12.12.2010
comment
Сравните рекурсивный алгоритм с рекурсивной реализацией этого алгоритма. Последнее всегда требует места в стеке, если это не пример хвостовой рекурсии. Первое зависит от того, как оно реализовано. - person Jason S; 12.12.2010