Réécriture d'une fonction récursive sans utiliser la récursivité

Je suis en train de réécrire du code existant dans un contexte où les appels récursifs ne sont pas facilement implémentés ni souhaités. (Et dans Fortran 77, si vous devez le savoir.) J'ai pensé à créer une pile à partir de zéro pour garder une trace des appels nécessaires, mais cela semble kludgy, et je préfère ne pas allouer de mémoire à un tableau dans les cas où la récursivité n'est pas profonde. (Je ne suis pas sûr que Fortran 77 supporte le dimensionnement dynamique des tableaux non plus.)Réécriture d'une fonction récursive sans utiliser la récursivité

D'autres suggestions pour une solution générale sur la façon de prendre une fonction évidemment récursive et de la réécrire de façon non récursive sans gaspiller d'espace sur une pile?

Un grand merci, Old MCST

Source

2010-12-12 Old McStopher

S'il ne se branche pas, vous pouvez généralement le réécrire en une simple boucle. Si elle se branche vous avez généralement besoin d'une pile – CodesInChaos

@CodeInChaos: une fonction récursive qui ne branche pas, par définition, ne reviendra jamais ... –

Devinez que j'ai mal utilisé le mot branche. Je veux dire appel lui-même plusieurs fois, de sorte que le graphique des appels devient un arbre avec des branches. Et ce n'est que mon expérience et pas toujours vrai. – CodesInChaos

Si votre code utilise la récursivité de queue (qui est, la fonction retourne le résultat de chaque appel récursif directement, sans aucun autre traitement), il est possible de réécrire la fonction impérieusement sans pile:

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

en:

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

Sans récursion de queue, l'utilisation d'une pile (ou d'un stockage intermédiaire similaire) est la seule solution.

Source

2010-12-12 14:17:42

Ceci est similaire à ce que je pensais, mais ne pouvait pas mettre en mots. Donc, dans mon cas particulier, j'ai un ensemble de données d'éléments qui devront chacun être testés pour une relation avec d'autres éléments de l'ensemble. Je pourrais passer dans la structure de données de tous les éléments, mais puisque chacun a besoin d'un traitement supplémentaire, je suppose que la pile est inévitable, oui? –

Cela dépend.Si le code est majoritairement "pour toutes les paires (a, b) si P (a, b) est vrai alors exécutez F (a, b)" vous pouvez vous en sortir en bouclant itérativement toutes les paires ... –

La plupart des fonctions récursives peuvent facilement être réécrites sous forme de boucles, à perdre de l'espace - qui dépend de la fonction, puisque beaucoup (mais pas tous) des algorithmes récursifs dépendent en fait de ce genre de stockage (bien que la version en boucle soit généralement plus efficace dans ces cas aussi).

Source

2010-12-12 14:15:59 Ofir

Prendre soin d'afficher une fonction récursive ne nécessitant pas d'espace sur la pile? Même pour ses arguments? –

@Nikita Rybak: une fonction en-queue récursive inline;) –

@Victor Oui, mais c'est sous une forme réécrite. Et Ofir affirme qu'il existe une fonction récursive qui ne nécessite pas de mémoire de pile. Donc, je suis curieux. –

La fonction récursive classique qui peut être écrit en boucle est la fonction de Fibonacci:

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

Mais sans memoization cela prend O (exp^N) avec O (N) de l'espace de pile.

Il peut être réécrite:

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

Mais cela implique la connaissance de la façon dont fonctionne la fonction, ne sais pas si elle peut être généralisée à un processus automatique.

Source

2010-12-12 16:51:54

Réécriture d'une fonction récursive sans utiliser la récursivité

Répondre

Questions connexes