Algorithmes de récursion: modèles et pratiques suggérés?

Question

J'écris un utilitaire qui réfléchit sur deux graphes d'objets et retourne une valeur pour indiquer si les graphes sont identiques ou non. Il m'a fait penser, y at-il un modèle généralement accepté pour l'écriture d'un algorithme de récursivité qui renvoie une valeur de certains où dans la récursivité?

Ma solution serait probablement utiliser un paramètre ref et ressembler à quelque chose comme ce code pseudo:

public static bool IsChanged(T current, T previous) 
{ 
    bool isChanged = false;   
    CheckChanged(current, previous, ref isChanged);   
    return isChanged ; 
} 


private static void CheckChanged(T current, T previous, ref isChanged) 
{ 
    //perform recursion 
    if (graphIsChanged) 
     isChanged = true; 
    else 
     CheckChanged(current, previous, ref isChanged); 
} 

Y at-il une meilleure/propre/façon plus efficace? Existe-t-il un modèle général pour une telle fonction?

Answer 1

Je ne vois aucun avantage de votre version par rapport à cette version très trivial:

public static bool IsChanged(T current, T previous) 
{ 
    //perform recursion 
    if (graphIsChanged) 
     return true; 
    else 
     return IsChanged(current, previous); 
} 

Comme un avantage supplémentaire, certains compilateurs sont capables d'utiliser l'optimisation des appels de queue pour transformer cette version en simple boucle, ce qui est plus efficace.

Answer 2

J'ai toujours été fan d'avoir une valeur de retour réelle à partir d'une fonction récursive, pas simplement passer une référence à une variable. Je ne suis pas vraiment sûr de ce que vous essayez de faire dans votre échantillon, mais pourquoi ne pas simplement retourner un bool de CheckChanged?

Answer 3

Il n'y a pas de modèle général pour les fonctions récursives. La seule exigence est que la fonction soit garantie pour atteindre un cas dégénéré (c'est-à-dire non récursif), de sorte que vous ne vous retrouvez pas avec une récursion infinie. D'une manière générale, l'utilisation d'une valeur de retour est probablement légèrement plus efficace que le passage d'un paramètre pointeur, mais cela dépendra du problème spécifique et du compilateur utilisé.

Dans tous les cas, de telles micro-optimisations sont rarement utiles. Concentrez-vous d'abord sur la meilleure complexité d'exécution, puis modifiez le code plus tard si vous vous retrouvez avec un problème de performance.

Answer 4

récursion La queue est non seulement plus efficace, il vous empêche de souffler la pile sur récursivité profonde: http://en.wikipedia.org/wiki/Tail_recursion

C'est-à-dire, il empêche « Stack Overflow » :)

http://en.wikipedia.org/wiki/Stack_overflow