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

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

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

Большое спасибо, Старого MCST

источник

2010-12-12 Old McStopher

Если это не ветка, вы можете переписать ее в простой цикл. Если это ветви, вам обычно нужен стек – CodesInChaos

@CodeInChaos: рекурсивная функция, которая не имеет ветви, по определению никогда не вернется ... –

Угадайте, что я неправильно использовал ветвь слова. Я имею в виду вызовы несколько раз, поэтому график вызовов становится деревом с ветвями. И это только мой опыт, а не всегда правда. – CodesInChaos

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

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

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

источник

2010-12-12 14:17:42

Это похоже на то, о чем я думал, но не мог выразить словами. Поэтому в моем конкретном случае у меня есть набор данных, каждый из которых должен быть протестирован для связи с другими элементами в наборе. Я мог бы передать структуру данных всех элементов, но поскольку каждая из них нуждается в дальнейшей обработке, я полагаю, что стек неизбежен, да? –

Зависит.Если код в основном «для всех пар (a, b), если P (a, b) истинно, тогда выполните F (a, b)», вы можете уйти с итерационным циклом по всем парам ... –

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

источник

2010-12-12 14:15:59 Ofir

Уход за отображением рекурсивной функции, не требующей места в стеке? Даже для его аргументов? –

@ Никита Рыбак: встроенная хвостовая рекурсивная функция;) –

@Victor Да, но это в переписанной форме. И Офир утверждает, что существует рекурсивная функция, не требующая памяти стека. Итак, мне любопытно. –

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

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

Но без запоминания это занимает O (ехр^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; 
}

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

источник

2010-12-12 16:51:54

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

ответ

Смежные вопросы