Les gars, j'ai beaucoup de mal à comprendre la récursivité à l'école. Chaque fois que le prof en parle, il me semble que je l'obtiens, mais dès que je l'essaie seul, il me souffle complètement la cervelle. J'essayais de résoudre les tours de Hanoi toute la nuit et j'ai complètement perdu la tête. Mon manuel a seulement environ 30 pages en récursivité, donc ce n'est pas trop utile. Est-ce que quelqu'un connaît des livres ou des ressources qui peuvent aider à clarifier ce sujet?
Réponses
Trop de publicités?
tpdi
Points
18427
Comment vider un vase contenant cinq fleurs?
Réponse: si le vase n'est pas vide, vous prenez une fleur et puis vous vide un vase contenant quatre fleurs.
Comment vider un vase contenant quatre fleurs?
Réponse: si le vase n'est pas vide, vous prenez une fleur et puis vous vide un vase contenant trois fleurs.
Comment vider un vase contenant trois fleurs?
Réponse: si le vase n'est pas vide, vous prenez une fleur et puis vous vide un vase contenant deux fleurs.
Comment vider un vase contenant deux fleurs?
Réponse: si le vase n'est pas vide, vous prenez une fleur et puis vous vide un vase contenant une fleur.
Comment vider un vase contenant une fleur?
Réponse: si le vase n'est pas vide, vous prenez une fleur et puis vous vide un vase contenant pas de fleurs.
Comment vider un vase contenant pas de fleurs?
Réponse: si le vase n'est pas vide, vous prenez une fleur mais le vase est vide, donc vous avez terminé.
C'est répétitif. Nous allons généraliser ce:
Comment vider un vase contenant de la N des fleurs?
Réponse: si le vase n'est pas vide, vous prenez une fleur et puis vous vide un vase contenant N-1 fleurs.
Hmm, peut-on voir que dans le code?
void emptyVase( int flowersInVase ) {
if( flowersInVase > 0 ) {
// take one flower and
emptyVase( flowersInVase - 1 ) ;
} else {
// the vase is empty, nothing to do
}
}
Hmm, ne pourrions-nous pas avoir fait juste que dans une boucle for?
Pourquoi oui, la récursivité peut être remplacé par itération, mais souvent la récursivité est plus élégant.
Parlons des arbres. En informatique, un arbre est une structure composée de nœuds, où chaque noeud a un certain nombre d'enfants qui sont aussi des nœuds, ou la valeur null. Un arbre binaire est un arbre fait de nœuds qui ont exactement deux enfants, généralement appelé "gauche" et "droite"; de nouveau, les enfants peuvent être des nœuds, ou la valeur null. Une racine est un nœud qui n'est pas l'enfant de n'importe quel autre nœud.
Imaginez qu'un nœud, en plus de ses enfants, a une valeur, un certain nombre, et d'imaginer que nous souhaitons à la somme de toutes les valeurs dans un arbre.
La somme de la valeur de tout un nœud, nous tenons à ajouter de la valeur du nœud lui-même de la valeur de ses gauche de l'enfant, le cas échéant, et la valeur de son droit à l'enfant, le cas échéant. Maintenant, rappelons que les enfants, s'ils ne sont pas nulles, sont aussi des nœuds.
Donc la gauche de l'enfant, nous tenons à ajouter de la valeur du nœud enfant lui-même de la valeur de ses gauche de l'enfant, le cas échéant, et la valeur de son droit à l'enfant, le cas échéant.
Donc la somme de la valeur de la gauche de l'enfant gauche de l'enfant, nous tenons à ajouter de la valeur du nœud enfant lui-même de la valeur de ses gauche de l'enfant, le cas échéant, et la valeur de son droit à l'enfant, le cas échéant.
Vous avez peut-être prévu où je vais avec cela, et aimerait voir un peu de code? OK:
struct node {
node* left;
node* right;
int value;
} ;
int sumNode( node* root ) {
// if there is no tree, its sum is zero
if( root == null ) {
return 0 ;
} else { // there is a tree
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
}
}
Notez qu'au lieu de explicitement les tests les enfants pour voir s'ils sont null ou des nœuds, nous venons de faire le récursive de la fonction de retour à zéro pour une valeur nulle nœud.
Alors disons que nous avons un arbre qui ressemble à ceci (les chiffres sont les valeurs, les barres obliques point d'enfants, et @ signifie que le pointeur pointe vers null):
5
/ \
4 3
/\ /\
2 1 @ @
/\ /\
@@ @@
Si nous appelons sumNode sur la racine (le nœud avec la valeur 5), nous obtenons:
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;
Nous allons étendre en place. Partout nous voyons sumNode, nous allons le remplacer par l'expansion de l'instruction de retour:
sumNode( node-with-value-5);
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;
return 5 + 4 + sumNode( node-with-value-2 ) + sumNode( node-with-value-1 )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + sumNode(null ) + sumNode( null )
+ sumNode( node-with-value-1 )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ sumNode( node-with-value-1 )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + sumNode(null ) + sumNode( null )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ 3 + sumNode(null ) + sumNode( null ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ 3 + 0 + 0 ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ 3 ;
return 5 + 4
+ 2 + 0 + 0
+ 1
+ 3 ;
return 5 + 4
+ 2
+ 1
+ 3 ;
return 5 + 4
+ 3
+ 3 ;
return 5 + 7
+ 3 ;
return 5 + 10 ;
return 15 ;
Voyons maintenant comment nous avons conquis une structure de profondeur arbitraire et "branchiness", en considérant que l'application répétée d'un composite modèle? chaque fois par le biais de notre sumNode fonction, nous avons traité avec un seul nœud, à l'aide d'un singe si/puis la branche, et deux simple retour des déclarations que presque écrit themsleves, directement à partir de notre cahier des charges?
How to sum a node:
If a node is null
its sum is zero
otherwise
its sum is its value
plus the sum of its left child node
plus the sum of its right child node
C'est la puissance de la récursivité.
Le vase à l'exemple ci-dessus est un exemple de la queue de la récursivité. Tout ce que la queue de la récursivité signifie est que, dans la fonction récursive, si nous recursed (qui est, si on appelle la fonction de nouveau), qui a été la dernière chose que nous avons fait.
L'exemple d'arbre n'a pas de queue récursive, car même si la dernière chose que nous avons fait a été de répéter le droit de l'enfant, avant de nous ne que nous recursed la gauche de l'enfant.
En fait, l'ordre dans lequel nous les avons appelés les enfants, et a ajouté l'actuel nœud de valeur n'a pas d'importance, parce que l'addition est commutative.
Maintenant, regardons une opération où l'ordre a de l'importance. Nous allons utiliser un arbre binaire de nœuds, mais cette fois, la valeur sera un personnage, pas un numéro.
Notre arbre ont une propriété particulière, que pour tout nœud, son personnage vient après (dans l'ordre alphabétique) le caractère détenus par la gauche de l'enfant et de l' avant (dans l'ordre alphabétique) le personnage tenu par son enfant.
Ce que nous voulons faire est d'imprimer l'arbre est l'ordre alphabétique. C'est facile à faire, compte tenu de l'arbre spécial de la propriété. Nous venons d'imprimer la gauche de l'enfant, puis le nœud du personnage, puis à droite de l'enfant.
Nous ne voulons pas seulement d'impression de bon gré mal gré, nous allons passer à notre fonction de quelque chose à imprimer sur. Ce sera un objet avec un print( char ) la fonction; nous n'avons pas besoin de vous soucier de la façon dont il fonctionne, c'est juste que lorsque l'impression est appelé, il va imprimer quelque chose, quelque part.
Nous allons voir que dans le code:
struct node {
node* left;
node* right;
char value;
} ;
// don't worry about this code
class Printer {
private ostream& out;
Printer( ostream& o ) :out(o) {}
void print( char c ) { out << c; }
}
// worry about this code
int printNode( node* root, Printer& printer ) {
// if there is no tree, do nothing
if( root == null ) {
return ;
} else { // there is a tree
printNode( root->left, printer );
printer.print( value );
printNode( root->right, printer );
}
Printer printer( std::cout ) ;
node* root = makeTree() ; // this function returns a tree, somehow
printNode( root, printer );
En plus de la commande de l'exploitation important, cet exemple montre que nous pouvons passer des choses dans une fonction récursive. La seule chose que nous avons à faire est de s'assurer que chaque appel récursif, nous continuons à le transmettre. Nous avons passé en un pointeur vers un noeud et d'une imprimante à la fonction, et à chaque appel récursif, nous sommes passés de "vers le bas".
Maintenant, si notre arbre ressemble à ceci:
k
/ \
h n
/\ /\
a j @ @
/\ /\
@@ i@
/\
@@
Que ferons-nous de l'impression?
From k, we go left to
h, where we go left to
a, where we go left to
null, where we do nothing and so
we return to a, where we print 'a' and then go right to
null, where we do nothing and so
we return to a and are done, so
we return to h, where we print 'h' and then go right to
j, where we go left to
i, where we go left to
null, where we do nothing and so
we return to i, where we print 'i' and then go right to
null, where we do nothing and so
we return to i and are done, so
we return to j, where we print 'j' and then go right to
null, where we do nothing and so
we return to j and are done, so
we return to h and are done, so
we return to k, where we print 'k' and then go right to
n where we go left to
null, where we do nothing and so
we return to n, where we print 'n' and then go right to
null, where we do nothing and so
we return to n and are done, so
we return to k and are done, so we return to the caller
Donc, si on regarde juste les lignes étaient nous avons imprimé:
we return to a, where we print 'a' and then go right to
we return to h, where we print 'h' and then go right to
we return to i, where we print 'i' and then go right to
we return to j, where we print 'j' and then go right to
we return to k, where we print 'k' and then go right to
we return to n, where we print 'n' and then go right to
Nous voyons que nous avons imprimé "ahijkn", qui est en effet dans l'ordre alphabétique.
Nous gérons pour imprimer un arbre entier, dans l'ordre alphabétique, tout en sachant comment faire pour imprimer un seul nœud dans l'ordre alphabétique. Ce qui est juste (parce que notre arbre a la particularité de commande les valeurs à gauche de l'ordre alphabétique, plus tard des valeurs) en sachant que pour imprimer la gauche de l'enfant avant l'impression de la valeur du nœud, et tto imprimer le droit de l'enfant après l'impression de la valeur du nœud.
Et c'est la puissance de la récursivité: être capable de faire des choses ensemble en connaissant seulement la manière de faire une partie de l'ensemble (et de savoir quand arrêter recursing).
Rappelant que, dans la plupart des langues, l'opérateur || ("ou") court-circuits lors de son premier opérande est vrai, le général de la fonction récursive est:
void recurse() { doWeStop() || recurse(); }
Luc M commentaires:
DONC, devraient créer un badge pour ce genre de réponse. Félicitations!
Merci, Luc! Mais, en fait, parce que j'ai édité cette réponse plus que quatre fois (pour ajouter le dernier exemple, mais surtout pour corriger les fautes de frappe et de le polir, taper sur un petit netbook clavier est dur), je ne peux pas obtenir plus de points. Qui peu me décourage de mettre autant d'efforts dans les futures réponses.
Voir mon commentaire ici: http://stackoverflow.com/questions/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699
Ólafur Waage
Points
40104
(Met le chapeau de blague, puisque personne ne l'a fait)
Si vous ne savez pas quelle récursion est, consultez cette question
cfisher
Points
4915
Votre cerveau a explosé parce qu'il a eu une récursion infinie. C'est une erreur de débutant.
Croyez le ou non, vous avez déjà comprendre la récursivité, vous êtes juste être tirée vers le bas par une commune, mais défectueux métaphore d'une fonction: une petite boîte avec des trucs qui entre et sort.
Pensez plutôt d'une tâche ou d'une procédure, telle que "en savoir plus sur la récursivité sur le net". C'est récursive et vous n'aurez aucun problème avec elle. Pour effectuer cette tâche, vous pouvez:
a) Lire un Google page de résultat pour "récursivité" b) une Fois que vous avez lu, suivre le premier lien sur lui et... un.1)Lire cette nouvelle page sur la récursivité b.1)une Fois que vous avez lu, suivre le premier lien sur lui et... un.2)Lire cette nouvelle page sur la récursivité b.2)une Fois que vous avez lu, suivre le premier lien sur lui et...
Comme vous pouvez le voir, vous avez fait récursive des trucs pour une longue période de temps sans aucun problème.
Pour combien de temps voulez-vous continuer à faire cette tâche? Jamais jusqu'à ce que votre cerveau explose? Bien sûr que non, vous vous arrêterez à un point donné, à chaque fois que vous croyez que vous avez terminé la tâche.
Il n'y a pas besoin de le spécifier lorsque vous demandant de "en savoir plus sur la récursivité sur le net", parce que vous êtes un homme et vous pouvez en déduire que par vous-même.
L'ordinateur ne pouvez pas déduire jack, de sorte que vous devez inclure explicitement la fin: "en savoir plus sur la récursivité sur le net, JUSQU'à ce que vous comprendre ou vous avez lu un maximum de 10 pages".
Vous aussi en déduire que vous devriez commencer à Google de la page de résultat pour "récursivité", et c'est là quelque chose d'un ordinateur ne peut pas le faire. La description complète de nos récursive tâche doit également prévoir de façon explicite le point de départ:
"en savoir plus sur la récursivité sur le net, JUSQU'à ce que vous comprendre ou vous avez lu un maximum de 10 pages et de commencer à www.google.com/search?q=recursion"
Analyser l'ensemble de la chose, je vous suggère d'essayer un de ces livres:
- Common Lisp: Une Douce Introduction au Calcul Symbolique. C'est le plus mignon de la non-explication mathématique de la récursivité.
- Le peu intrigant.
dar7yl
Points
2387
Pour comprendre la récursivité, tout ce que vous avez à faire est de regarder sur l'étiquette de votre bouteille de shampoing:
function repeat()
{
rinse();
lather();
repeat();
}
Le problème avec ceci est qu'il n'y a pas de condition de terminaison, et la récursivité se répétera indéfiniment, ou jusqu'à ce que vous n'ayez plus de shampooing ou d'eau chaude (conditions de terminaison externes, semblables à souffler votre pile).
Chris Upchurch
Points
10484
Si vous voulez un livre qui explique bien la récursion en termes simples, jetez un coup d'œil à Gödel, Escher, Bach: Une éternelle tresse d'or par Douglas Hofstadter, en particulier le chapitre 5. En plus de la récursivité, cela explique bien un certain nombre de concepts complexes en informatique et en mathématiques d'une manière compréhensible, avec une explication s'appuyant sur une autre. Si vous n'avez pas eu beaucoup d'exposition à ce genre de concepts auparavant, cela peut être un livre assez hallucinant.
