Qu'est-ce que la récursivité et quand devrais-je l'utiliser?

Question

L'un des sujets qui semble apparaître régulièrement sur les listes de diffusion et les discussions en ligne concerne les avantages (ou le manque de pertinence) de l'obtention d'un diplôme en informatique. Un argument qui semble se répéter à maintes reprises pour la partie négative est qu'elle code depuis un certain nombre d'années et qu'elle n'a jamais utilisé la récursivité.

La question est donc:

1. Qu'est-ce que la récursion?
2. Quand utiliserais-je la récursivité?
3. Pourquoi les gens n'utilisent-ils pas la récursivité?

Answer 1

Il y a un certain nombre de bonnes explications de la récursivité dans ce fil, cette réponse, c'est pourquoi vous ne devriez pas l'utiliser dans la plupart des langues.* Dans la plupart des grandes impératif implémentations de langue (c'est à dire tous les grands de la mise en œuvre de C, C++, Basic, Python, Ruby,Java et C#) itération est infiniment préférable à la récursivité.

Pour comprendre pourquoi, à pied à travers les étapes ci-dessus langues à utiliser pour l'appel d'une fonction:

1. l'espace est sculptée sur la pile pour les arguments de la fonction et les variables locales
   • les arguments de la fonction sont copiés dans ce nouvel espace
   • le contrôle passe à la fonction
   • le code de fonction s'exécute
   • le résultat de la fonction est copié dans une valeur de retour
   • la pile est remonté à sa position précédente
   • le contrôle revient à l'endroit où la fonction a été appelée

Toutes ces étapes prennent du temps, généralement un peu plus qu'il n'en faut pour parcourir une boucle. Cependant, le vrai problème est dans l'étape #1. Lorsque de nombreux programmes de démarrage, ils assignent un seul morceau de la mémoire de leur pile, et quand ils sont à court de mémoire (souvent, mais pas toujours en raison de la récursivité), le programme se bloque à cause d'un débordement de pile.

Donc, dans ces langues, la récursivité est plus lent, et il vous rend vulnérable à s'écraser. Il y a encore quelques arguments pour l'utilisant bien. En général, le code écrit de manière récursive est plus courte et un peu plus élégante, une fois que vous savez comment faire pour le lire.

Il y a une technique que la langue exécutants peuvent utiliser appelée queue appel d'optimisation qui permet d'éliminer certaines classes de débordement de la pile. Mettre succinctement: si une fonction de retour d'expression est simplement le résultat d'un appel de fonction, alors vous n'avez pas besoin d'ajouter un nouveau niveau dans la pile, vous pouvez les réutiliser pour la fonction appelée. Malheureusement, peu de langage impératif-implémentations de queue-appel d'optimisation intégré.

* J'aime la récursivité. Mon préféré statique de la langue ne pas utiliser de boucles à tous, la récursivité est la seule façon de faire quelque chose à plusieurs reprises. Je ne pense pas que la récursivité est généralement une bonne idée dans des langues qui ne sont pas à l'écoute pour elle.

** Par la voie de Mario, le nom typique pour votre ArrangeString fonction "joindre", et je serais surpris si la langue de votre choix n'est pas encore mise en œuvre.

Answer 2

Exemple anglais simple de récursion.

 A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her a story about a little weasel... 
            who fell asleep.
        ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.
 

Answer 3

Au sens informatique le plus fondamental, la récursivité est une fonction qui s’appelle elle-même. Supposons que vous ayez une structure de liste chaînée:

 struct Node {
    Node* next;
};
 

Et vous voulez savoir combien de temps dure une liste chaînée, vous pouvez le faire avec la récursivité:

 int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}
 

(Cela pourrait bien sûr être fait avec une boucle for, mais est utile pour illustrer le concept)

Answer 4

Chaque fois qu'une fonction s'appelle elle-même, la création d'une boucle, alors que c'est la récursivité. Comme avec n'importe quoi il y a de bons usages et à de mauvais usages de la récursivité.

Le plus simple est de la queue de la récursivité, où la dernière ligne de la fonction est un appel à elle-même:

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

Cependant, c'est un boiteux, presque inutile exemple, car il peut facilement être remplacé par des plus efficaces itération. Après tout, la récursivité souffre d'un appel de fonction, les frais généraux, qui, dans l'exemple ci-dessus pourrait être importante par rapport à l'exploitation, à l'intérieur de la fonction elle-même.

Ainsi, l'ensemble de raison de faire de la récursivité plutôt que d'itération devrait être de prendre avantage de la pile d'appel pour faire quelques trucs forts. Par exemple, si vous appelez une fonction plusieurs fois avec des paramètres différents à l'intérieur de la boucle, alors que c'est un moyen pour accomplir la ramification. Un exemple classique est le triangle de Sierpinski.

Vous pouvez dessiner un de ces très simplement avec la récursivité, où la pile d'appel des succursales dans 3 directions:

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

Si vous essayez de faire la même chose avec des itérations je pense que vous trouverez cela prend beaucoup plus de code à accomplir.

D'autres cas d'utilisation courants peuvent inclure la traversée des hiérarchies, par exemple un site web crawlers, répertoire des comparaisons, etc.

Conclusion

En termes pratiques, la récursivité qui fait le plus de sens quand vous en avez besoin itératif de ramification.

Answer 5

La récursivité est une méthode de résolution de problèmes basée sur la division et de conquête de la mentalité. L'idée de base est que vous prenez le problème d'origine et de le diviser en plus petites (plus facilement résolu) instances de lui-même, de résoudre ces petites instances (habituellement en utilisant le même algorithme de nouveau), puis remonter vers la solution finale.

L'exemple canonique est une routine pour générer la Factorielle de n. La Factorielle de n est calculé en multipliant tous les nombres entre 1 et n. Une solution itérative en C# ressemble à ceci:

public int Fact(int n)

Il n'y a rien de surprenant au sujet de la solution itérative et il doit faire sens pour quiconque est familier avec le C#.

La solution récursive est trouvé en reconnaissant que le nième Factorielle est n * Fact(n-1). Ou pour le dire d'une autre façon, si vous savez ce que la Factorielle du nombre est, vous pouvez calculer la suivante. Voici la solution récursive en C#:

La première partie de cette fonction est connue comme un Cas de Base (ou parfois de la Garde de la Clause) et tout ce qui empêche l'algorithme de running à tout jamais. Elle retourne la valeur 1 lorsque la fonction est appelée avec une valeur de 1 ou moins. La deuxième partie est plus intéressante et est connu comme le Récursive Étape. Ici, nous appelons la même méthode avec un peu modifié le paramètre (nous décrémenter par 1), puis multiplier le résultat avec notre copie de n.

Lors de la première rencontre, ce peut être une sorte de confusion, donc il est instructif d'examiner comment il fonctionne lorsque vous exécutez. Imaginez que nous appelons FactRec(5). Nous entrons dans la routine, ne sont pas récupérés par le cas de base et on se retrouve donc comme ceci:

{

Si nous re-entrer dans la méthode avec le paramètre 4 nous sommes de nouveau n'est pas stoppé par le gardien de la clause et donc nous retrouver à:

Si l'on substitue cette valeur de retour dans la valeur de retour ci-dessus nous obtenons

  int fact = 1;

Cela devrait vous donner une idée de la façon dont la solution finale est arrivé au nous allons donc la voie rapide et montrer à chaque étape sur le chemin vers le bas:

La finale de substitution se produit lorsque le cas de base est déclenchée. À ce stade, nous avons une simple algrebraic formule pour résoudre qui correspond directement à la définition des Factorielles, en premier lieu.

Il est instructif de noter que chaque appel à la méthode les résultats dans une base de cas a été déclenché ou un appel à la même méthode, où les paramètres sont plus proches d'une base de cas (souvent appelé un appel récursif). Si ce n'est pas le cas, alors la méthode s'exécute indéfiniment.