L'idée de récursion n'est pas très courante dans le monde réel. Cela semble donc un peu déroutant pour les programmeurs débutants. Bien que, je suppose, ils s’habituent au concept progressivement. Alors, quelle peut être une bonne explication pour qu'ils puissent saisir l'idée facilement?
74
Réponses:
Pour expliquer la récursivité , j'utilise une combinaison d'explications différentes, généralement pour essayer à la fois:
Pour commencer, Wolfram | Alpha le définit plus simplement que Wikipedia :
Mathématiques
Si votre élève (ou la personne que vous expliquez aussi, je dirai désormais élève) a au moins quelques connaissances en mathématiques, il est évident qu'ils ont déjà rencontré la récursivité en étudiant les séries et leur notion de récursivité et leur relation de récurrence .
Une très bonne façon de commencer est alors de démontrer avec une série et de dire que c'est tout simplement ce qu'est la récursion:
Habituellement, vous obtenez soit "hein heh, whatev '" au mieux car ils ne l'utilisent toujours pas, soit plus probablement un ronflement très profond.
Exemples de codage
Pour le reste, il s’agit en fait d’une version détaillée de ce que j’ai présenté dans l’ addendum de ma réponse à la question que vous avez évoquée concernant les pointeurs (mauvais jeu de mots).
A ce stade, mes étudiants savent généralement comment imprimer quelque chose à l'écran. En supposant que nous utilisons C, ils savent comment imprimer un seul caractère avec
write
ouprintf
. Ils connaissent également les boucles de contrôle.J'ai habituellement recours à quelques problèmes de programmation répétitifs et simples jusqu'à ce qu'ils l'obtiennent:
Factorielle
Factorial est un concept mathématique très simple à comprendre, et sa mise en œuvre est très proche de sa représentation mathématique. Cependant, ils pourraient ne pas l'obtenir au début.
Alphabets
La version alphabet est intéressante pour leur apprendre à réfléchir à la mise en ordre de leurs déclarations récursives. Comme avec les pointeurs, ils vous jetteront des lignes au hasard. Le but est de les amener à réaliser qu’une boucle peut être inversée en modifiant les conditions OU en inversant simplement l’ordre des instructions dans votre fonction. C'est là que l'impression de l'alphabet est utile, car c'est quelque chose de visuel pour eux. Demandez-leur simplement d’écrire une fonction imprimant un caractère pour chaque appel et s’appelant récursivement pour écrire le suivant (ou le précédent).
Amateurs de FP, oubliez le fait qu'imprimer des choses dans le flux de sortie est un effet secondaire pour le moment ... Ne soyons pas trop ennuyeux sur le front de la FP. (Mais si vous utilisez un langage prenant en charge les listes, n'hésitez pas à concaténer une liste à chaque itération et à imprimer le résultat final. Mais d'habitude, je les commence avec C, ce qui n'est malheureusement pas le meilleur pour ce type de problèmes et de concepts.) .
Exponentiation
Le problème de l'exponentiation est légèrement plus difficile ( à ce stade d'apprentissage). Évidemment, le concept est exactement le même que pour une factorielle et il n’ya pas de complexité supplémentaire… sauf que vous avez plusieurs paramètres. Et cela suffit généralement à décontenancer les gens et à les décontenancer au début.
Sa forme simple:
peut être exprimé comme ceci par récurrence:
Plus fort
Une fois que ces problèmes simples ont été montrés ET réimplémentés dans des tutoriels, vous pouvez donner des exercices un peu plus difficiles (mais très classiques):
Note: Encore une fois, certains d'entre eux ne sont vraiment pas plus difficiles… Ils abordent simplement le problème sous le même angle, ou sous un angle légèrement différent. Mais la pratique rend parfait.
Aides
Une référence
Certaines lectures ne font jamais de mal. Au début, ils se sentiront encore plus perdus. C'est le genre de chose qui pousse sur vous et qui se cache derrière votre tête jusqu'au jour où vous réalisez que vous l'avez enfin. Et puis vous repensez à ces choses que vous lisez. La récursion , la récursion en informatique et les pages de relation de récurrence sur Wikipedia suffiraient pour le moment.
Niveau / profondeur
En supposant que vos étudiants n’ont pas beaucoup d’expérience en codage, fournissez des talons de code. Après les premières tentatives, donnez-leur une fonction d'impression capable d'afficher le niveau de récursivité. Imprimer la valeur numérique du niveau aide.
Le diagramme empilable
Il est également utile d'indenter un résultat imprimé (ou la sortie du niveau), car cela donne une autre représentation visuelle de ce que fait votre programme, en ouvrant et en fermant des contextes de pile, tels que des tiroirs ou des dossiers dans un explorateur de système de fichiers.
Acronymes récursifs
Si votre élève est déjà un peu familiarisé avec la culture informatique, il se peut qu'il utilise déjà des projets / logiciels avec des noms utilisant des acronymes récursifs . C'est une tradition qui existe depuis quelque temps, en particulier dans les projets GNU. Quelques exemples incluent:
Récursif:
Mutuellement récursif:
Demandez-leur d'essayer de trouver les leurs.
De même, il existe de nombreuses occurrences d'humour récursif, comme la correction de recherche récursive de Google . Pour plus d'informations sur la récursivité, lisez cette réponse .
Pièges et apprentissage ultérieur
Certaines questions avec lesquelles les gens ont généralement du mal et pour lesquelles vous devez connaître les réponses.
Pourquoi, oh mon Dieu pourquoi ???
Pourquoi ferais-tu ça? Une raison valable mais non évidente est qu'il est souvent plus simple d'exprimer un problème de cette façon. Une raison peu évidente, mais évidente, est qu'il faut souvent moins de dactylographie (ne leur donnez pas la sensation d'être si mal pour utiliser simplement la récursivité ...).
Certains problèmes sont définitivement plus faciles à résoudre avec une approche récursive. En règle générale, tout problème que vous pouvez résoudre à l'aide d'un paradigme Divide and Conquer convient à un algorithme de récursion à plusieurs branches.
C'est quoi encore N ??
Pourquoi mon
n
ou (quel que soit le nom de votre variable) est différent à chaque fois? Les débutants ont généralement du mal à comprendre ce que sont une variable et un paramètre, et comment les éléments nommésn
dans votre programme peuvent avoir des valeurs différentes. Alors maintenant, si cette valeur est dans la boucle de contrôle ou la récursivité, c'est encore pire! Soyez gentil et n'utilisez pas les mêmes noms de variable partout et indiquez clairement que les paramètres ne sont que des variables .Conditions de fin
Comment puis-je déterminer mon état final? C'est facile, demandez-leur de dire les étapes à haute voix. Par exemple, pour la factorielle, commencez par 5, puis 4, puis ... jusqu'à 0.
Le diable est dans les détails
Ne parlez pas trop tôt de choses comme l’ optimisation des appels de queue . Je sais, je sais, le coût total de possession est bien, mais ils s'en moquent au début. Donnez-leur un peu de temps pour bien comprendre le processus, de manière à ce qu’il fonctionne pour eux. N'hésitez pas à briser leur monde plus tard, mais donnez-leur une pause.
De même, ne parlez pas directement de la première lecture de la pile d'appels et de sa consommation de mémoire et ... bien ... du débordement de pile . Je donne souvent des leçons particulières à des étudiants qui me montrent des conférences où ils ont 50 diapositives sur tout ce qu'il y a à savoir sur la récursion, alors qu'ils peuvent à peine écrire une boucle correctement à ce stade. Voilà un bon exemple de la façon dont une référence aidera plus tard, mais qui pour l’instant vous confond profondément.
Mais s'il vous plaît, précisez, en temps voulu, qu'il existe des raisons de choisir la voie itérative ou récursive .
Récursion mutuelle
Nous avons vu que les fonctions peuvent être récursives, et même qu’elles peuvent avoir plusieurs points d’appel (8 reines, Hanoi, Fibonacci ou même un algorithme d’exploration pour un dragueur de mines). Mais qu'en est-il des appels mutuellement récursifs ? Commencez par les mathématiques ici aussi.
f(x) = g(x) + h(x)
oùg(x) = f(x) + l(x)
eth
etl
juste faire des choses.Commencer par des séries mathématiques facilite l'écriture et la mise en œuvre car le contrat est clairement défini par les expressions. Par exemple, les séquences féminine et masculine de Hofstadter :
Cependant, en termes de code, il convient de noter que la mise en œuvre d'une solution mutuellement récursive conduit souvent à une duplication du code et devrait plutôt être simplifiée en un seul formulaire récursif (Voir La résolution de Chaque puzzle de Sudoku par Peter Norvig .
la source
static unsigned int vote = 1;
de moi. Pardonnez l'humour statique, si vous voulez :) C'est la meilleure réponse à ce jour.L'appel d'une fonction à partir de cette même fonction.
la source
La récursivité est une fonction qui s’appelle elle-même.
Il est important de savoir comment l’utiliser, quand l’utiliser et comment éviter une mauvaise conception, ce qui vous oblige à l’essayer vous-même et à comprendre ce qui se passe.
La chose la plus importante à savoir est de faire très attention à ne pas créer une boucle qui ne se termine jamais. La réponse de pramodc84 à votre question a cette erreur: elle ne se termine jamais ...
Une fonction récursive doit toujours rechercher une condition pour déterminer si elle doit se rappeler ou non.
L'exemple le plus classique pour utiliser la récursivité consiste à utiliser un arbre sans aucune limite statique en profondeur. C'est une tâche que vous devez utiliser la récursivité.
la source
a
s’appelle toujours elle-même, juste indirectement (en appelantb
).La programmation récursive consiste à réduire progressivement un problème afin de résoudre plus facilement des versions de lui-même.
Chaque fonction récursive a tendance à:
Lorsque l'étape 2 est antérieure à 3 et que l'étape 4 est triviale (concaténation, somme ou rien), cela active la récursion de la queue . L'étape 2 doit souvent suivre l'étape 3, car les résultats du ou des sous-domaines du problème peuvent être nécessaires pour achever l'étape en cours.
Prendre la traversée d'un arbre binaire simple. La traversée peut être faite en pré-commande, en commande ou en post-commande, selon les besoins.
Pré-commande: BAC
En ordre: ABC
Post-commande: ACB
De très nombreux problèmes récursifs sont des cas spécifiques d'une opération de carte , ou un repli : la compréhension de ces deux opérations seulement peut permettre de mieux comprendre les bons cas d'utilisation de la récursivité.
la source
Le PO a déclaré que la récursivité n'existait pas dans le monde réel, mais je vous prie de différer.
Prenons la vraie 'opération' de découper une pizza. Vous avez sorti la pizza du four et pour la servir, vous devez la couper en deux, puis couper ces moitiés en deux, puis encore une fois couper les moitiés résultantes en deux.
L'opération consistant à couper la pizza que vous effectuez encore et encore jusqu'à obtenir le résultat souhaité (le nombre de tranches). Et pour des raisons d’argumentation, disons qu’une pizza non coupée est une tranche en soi.
Voici un exemple en Ruby:
Ainsi, les opérations dans le monde réel consistent à couper une pizza et la récursion fait la même chose encore et encore jusqu'à ce que vous obteniez ce que vous voulez.
Les opérations que vous constaterez que vous pouvez implémenter avec des fonctions récursives sont les suivantes:
Je recommande d'écrire un programme pour rechercher un fichier en fonction de son nom et essayer d'écrire une fonction qui s'appelle jusqu'à ce qu'il soit trouvé, la signature ressemblerait à ceci:
find_file_by_name(file_name_we_are_looking_for, path_to_look_in)
Donc, vous pourriez l'appeler comme ceci:
find_file_by_name('httpd.conf', '/etc') # damn it i can never find apache's conf
À mon avis, il s’agit simplement d’une mécanique de programmation, un moyen de supprimer intelligemment les doubles emplois. Vous pouvez réécrire cela en utilisant des variables, mais c'est une solution plus «agréable». Il n'y a rien de mystérieux ou difficile à ce sujet. Vous allez écrire quelques fonctions récursives, il va cliquer et huzzah une autre astuce mécanique dans votre boîte à outils de programmation.
Crédit supplémentaire L'
cut_pizza
exemple ci-dessus vous donnera une erreur de niveau de pile trop profonde si vous lui demandez un nombre de tranches qui n'est pas une puissance de 2 (c'est-à-dire 2 ou 4 ou 8 ou 16). Pouvez-vous le modifier pour que si quelqu'un demande 10 tranches, il ne fonctionnera pas pour toujours?la source
Ok, je vais essayer de garder cela simple et concis.
Les fonctions récursives sont des fonctions qui s’appellent. La fonction récursive comprend trois choses:
Le meilleur moyen d'écrire des méthodes récursives est de penser à la méthode que vous essayez d'écrire comme un exemple simple ne gérant qu'une boucle du processus sur lequel vous souhaitez effectuer une itération, puis ajoutez l'appel à la méthode elle-même et ajoutez quand vous le souhaitez. mettre fin. Le meilleur moyen d'apprendre est de pratiquer comme toutes choses.
Puisqu'il s'agit d'un site Web pour programmeurs, je m'abstiendrai d'écrire du code, mais voici un bon lien
si vous avez cette blague, vous obtenez ce que signifie récursivité.
la source
La récursivité est un outil qu'un programmeur peut utiliser pour appeler un appel de fonction sur lui-même. La séquence de Fibonacci est l'exemple type de l'utilisation de la récursivité.
La plupart des codes récursifs, sinon tous, peuvent être exprimés sous forme de fonction itérative, mais ils sont généralement compliqués. Les structures de données telles que les arbres, les arbres de recherche binaires et même le tri rapide sont de bons exemples d'autres programmes récursifs.
La récursion est utilisée pour rendre le code moins désordonné. N'oubliez pas qu'il est généralement plus lent et nécessite plus de mémoire.
la source
J'aime utiliser celui-ci:
Comment marchez-vous au magasin?
Si vous êtes à l'entrée du magasin, passez-le simplement. Sinon, faites un pas, puis continuez jusqu'au magasin.
Il est essentiel d'inclure trois aspects:
Nous utilisons beaucoup la récursion dans la vie quotidienne; nous ne pensons tout simplement pas de cette façon.
la source
for
boucle bien écrite en une fonction récursive inutile.Le meilleur exemple que je voudrais vous montrer est le langage de programmation C de K & R. Dans ce livre (et je cite de mémoire), l'entrée dans la page d'index de la récursion (seule) répertorie la page réelle où ils parlent de récursivité et la page d'index aussi.
la source
Josh K a déjà mentionné les poupées Matroshka . Supposons que vous souhaitiez apprendre quelque chose que seule la poupée la plus petite sait. Le problème est que vous ne pouvez pas lui parler directement, car elle habite à l’ origine dans la plus grande poupée qui, sur la première image, est placée à sa gauche. Cette structure va comme ça (une poupée habite à l'intérieur de la poupée la plus grande) jusqu'à ne se retrouver qu'avec la plus grande.
La seule chose que vous puissiez faire est donc de poser votre question à la plus grande des poupées. La poupée la plus grande (qui ne connaît pas la réponse) devra passer votre question à la poupée la plus courte (qui, sur la première image, est à sa droite). Comme elle n'a pas non plus la réponse, elle doit demander à la prochaine poupée plus courte. Cela ira comme ça jusqu'à ce que le message atteigne la poupée la plus courte. La poupée la plus courte (qui est la seule à connaître la réponse secrète) transmettra la réponse à la prochaine grande poupée (située à sa gauche), qui la transmettra à la prochaine grande poupée ... et cela se poursuivra jusqu'à la réponse. atteint sa destination finale, qui est la plus grande poupée et enfin ... vous :)
C'est ce que fait vraiment la récursivité. Une fonction / méthode s’appelle jusqu’à obtenir la réponse attendue. C'est pourquoi, lorsque vous écrivez du code récursif, il est très important de décider du moment auquel la récursion doit prendre fin.
Ce n'est pas la meilleure explication, mais cela aide, espérons-le.
la source
Récursion n. - Un modèle de conception d'algorithme où une opération est définie en termes d'elle-même.
L'exemple classique consiste à trouver la factorielle d'un nombre, n !. 0! = 1, et pour tout autre nombre naturel N, la factorielle de N est le produit de tous les nombres naturels inférieurs ou égaux à N. Donc, 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720. Cette définition de base vous permettrait de créer une solution itérative simple:
Cependant, examinez à nouveau l'opération. 6! = 6 * 5 * 4 * 3 * 2 * 1. Par la même définition, 5! = 5 * 4 * 3 * 2 * 1, ce qui signifie que nous pouvons dire 6! = 6 * (5!). À tour de rôle, 5! = 5 * (4!) Et ainsi de suite. Ce faisant, nous réduisons le problème à une opération effectuée sur le résultat de toutes les opérations précédentes. Cela se réduit finalement à un point, appelé cas de base, où le résultat est connu par définition. Dans notre cas, 0! = 1 (dans la plupart des cas, nous pourrions également dire que 1! = 1). En informatique, il nous est souvent permis de définir des algorithmes de manière très similaire, en faisant appeler la méthode elle-même et en lui transmettant une entrée plus petite, réduisant ainsi le problème de nombreuses récursions à un scénario de base:
Cela peut, dans de nombreuses langues, être encore simplifié à l'aide de l'opérateur ternaire (parfois considéré comme une fonction Iif dans des langues ne fournissant pas l'opérateur en tant que tel):
Avantages:
Désavantages:
la source
L’exemple que j’utilise est un problème que j’ai rencontré dans la vie réelle. Vous avez un conteneur (par exemple, un gros sac à dos que vous avez l'intention d'emporter en voyage) et vous souhaitez connaître le poids total. Vous avez dans le conteneur deux ou trois objets en vrac et d'autres conteneurs (par exemple, des sacs de rangement). Le poids total du conteneur correspond évidemment au poids du conteneur vide plus le poids de tout ce qu'il contient. Pour les articles en vrac, vous pouvez simplement les peser, et pour les sacs, vous pouvez simplement les peser ou vous pouvez dire "le poids de chaque sac est le poids du conteneur vide plus le poids de tout ce qu'il contient". Et puis vous continuez à aller dans des conteneurs dans des conteneurs et ainsi de suite jusqu'à ce que vous arriviez à un point où il ne reste que des objets en vrac dans un conteneur. C'est la récursion.
Vous pensez peut-être que cela ne se produit jamais dans la vie réelle, mais imaginez que vous essayez de compter ou d’additionner les salaires des personnes d’une société ou d’une division donnée, qui regroupe des personnes travaillant pour la société, des personnes de divisions, puis les divisions il y a des départements et ainsi de suite. Ou les ventes dans un pays qui a des régions, dont certaines ont des sous-régions, etc. Ces problèmes se produisent tout le temps dans les affaires.
la source
La récursivité peut être utilisée pour résoudre beaucoup de problèmes de comptage. Par exemple, supposons que vous ayez un groupe de n personnes à une fête (n> 1) et que tout le monde serre la main des autres une seule fois. Combien de poignées de main ont lieu? Vous savez peut-être que la solution est C (n, 2) = n (n-1) / 2, mais vous pouvez résoudre récursivement comme suit:
Supposons qu'il n'y ait que deux personnes. Ensuite (par inspection), la réponse est évidemment 1.
Supposons que vous avez trois personnes. Choisissez une personne et notez qu’elle serre la main de deux autres personnes. Après cela, il suffit de compter les poignées de main entre les deux autres personnes. Nous l’avons déjà fait tout à l’heure, et c’est 1. La réponse est donc 2 + 1 = 3.
Supposons que vous avez n personnes. En suivant la même logique qu'auparavant, il est (n-1) + (nombre de poignées de main entre n-1 personnes). En développant, on obtient (n-1) + (n-2) + ... + 1.
Exprimé comme une fonction récursive,
f (2) = 1
f (n) = n-1 + f (n-1), n> 2
la source
Dans la vie (par opposition à un programme informatique), la récursivité se produit rarement sous notre contrôle direct, car cela peut être déroutant. En outre, la perception a tendance à porter sur les effets secondaires plutôt que sur la fonctionnalité pure. Par conséquent, si une récursion se produit, il est possible que vous ne le remarquiez pas.
La récursivité se produit cependant ici dans le monde. Beaucoup.
Un bon exemple est (une version simplifiée du) cycle de l’eau:
C'est un cycle qui fait en sorte que le soi se reproduise. C'est récursif.
Un autre endroit où vous pouvez avoir de la récursion est l'anglais (et le langage humain en général). Vous ne le reconnaîtrez peut-être pas au début, mais la façon dont nous pouvons générer une phrase est récursive, car les règles nous permettent d'intégrer une instance d'un symbole dans une autre instance du même symbole.
De l'instinct de langue de Steven Pinker:
C'est une phrase entière qui contient d'autres phrases entières:
Pour comprendre la phrase complète, il faut comprendre des phrases plus petites, qui utilisent le même ensemble de ruses mentales pour être comprises comme une phrase complète.
Pour comprendre la récursivité du point de vue de la programmation, il est plus simple d’examiner un problème qui peut être résolu avec la récursivité et de comprendre pourquoi il devrait en être ainsi et ce que cela signifie que vous devez faire.
Pour l'exemple, j'utiliserai la plus grande fonction de diviseur commune, ou gcd en abrégé.
Vous avez vos deux chiffres
a
etb
. Pour trouver leur gcd (en supposant que ni est 0), vous devez vérifier sia
est divisible égalementb
. Si c’est alorsb
le gcd, sinon vous devez vérifier le gcdb
et le reste dea/b
.Vous devriez déjà être en mesure de voir qu’il s’agit d’une fonction récursive, puisque la fonction gcd appelle la fonction gcd. Juste pour le marteler chez nous, le voici en c # (encore une fois, en supposant que 0 ne soit jamais passé en paramètre):
Dans un programme, il est important d’avoir une condition d’arrêt pour que votre fonction ne se reproduise plus jamais, ce qui finira par provoquer un débordement de pile!
La raison d'utiliser la récursion ici, plutôt qu'une boucle while ou une autre construction itérative, est que lorsque vous lisez le code, il vous indique ce qu'il fait et ce qui va se passer ensuite. Il est donc plus facile de savoir s'il fonctionne correctement. .
la source
Voici un exemple concret de récursivité.
Laissez-les imaginer qu'ils ont une collection de bandes dessinées et vous allez tout mélanger. Attention - s'ils ont vraiment une collection, ils peuvent vous tuer instantanément lorsque vous mentionnez simplement l'idée de le faire.
Maintenant, laissez-les trier cette grosse pile de bandes dessinées non triées à l'aide de ce manuel:
La bonne chose ici est: quand ils sont à des problèmes simples, ils ont le "cadre de pile" complet avec les piles locales visibles devant eux sur le sol. Donnez-leur plusieurs impressions du manuel et mettez-en de côté chaque niveau de pile avec une marque à l'endroit où vous vous trouvez actuellement (c.-à-d. L'état des variables locales), afin que vous puissiez continuer là-bas sur chaque élément terminé.
En gros, la récursivité consiste à: exécuter le même processus, mais à un niveau de détail plus fin, plus vous y entrez.
la source
La récursivité est un moyen très concis d’exprimer quelque chose qui doit être répété jusqu’à atteindre quelque chose.
la source
Pas un anglais simple, pas vraiment des exemples réels, mais deux manières d’apprendre la récursion en jouant:
la source
Une belle explication de la récursivité est littéralement "une action qui se reproduit de l'intérieur".
Considérez un peintre en train de peindre un mur, c’est récursif parce que l’action est «peindre une bande du sol au sol, puis glisser légèrement vers la droite et peindre une bande du plafond au sol plutôt que de glisser légèrement vers la droite et dépouillez-vous du plafond au sol que glissez un peu à droite et (etc)))) ".
Sa fonction paint () s’appelle sans cesse pour constituer sa plus grande fonction paint_wall ().
J'espère que ce pauvre peintre a une sorte de condition d'arrêt :)
la source