[Jouer de la musique] 

DOUG LLOYD: Vous pensez probablement que code est juste utilisé pour accomplir une tâche. Vous écrivez-le. Il fait quelque chose. Voilà à peu près tout. 

Vous compilez. Vous exécutez le programme. Vous êtes bon pour aller. 

Mais croyez-le ou pas, si vous codez pendant une longue période, vous pourriez effectivement venu pour voir Code comme quelque chose qui est beau. Il résout un problème dans une façon très intéressante, ou il ya juste quelque chose de vraiment ordonnée au sujet de la façon dont elle regarde. Vous pourriez être riez à moi, mais il est vrai. Et récursion est une façon de sorte d'obtenir cette idée de la belle, le code élégant prospectifs. Il résout les problèmes d'une manière qui sont intéressants, faciles à visualiser, et étonnamment court. 

Les travaux façon de récurrence est une fonction récursive est défini comme étant une fonction qui appelle lui-même dans le cadre de son exécution. Cela peut sembler un peu étrange, et nous verrons un peu sur la façon dont cela fonctionne dans un moment. Mais encore une fois, ceux-ci procédures récursives sont va être si élégant parce qu'ils vont Pour résoudre ce problème sans ayant toutes ces autres fonctions ou ces longues boucles. Vous verrez que ces récursive procédures vont regarder si court. Et ils vont vraiment faire votre code air beaucoup plus belle. 

Je vais vous donner un exemple de cette façon de voir une procédure récursive peut être définie. Donc, si vous êtes familier avec ce à partir de la classe de mathématiques il ya plusieurs années, Il ya quelque chose appelé le fonction factorielle, qui est habituellement notée comme un point d'exclamation, qui est définie sur tous les entiers positifs. Et la façon dont n factorielle est calculée est vous multipliez tous les nombres inférieurs à ou égal à n together-- tous les entiers de moins de ou égal à n ensemble. 

Donc 5 factorielle est 5 fois 4 fois 3 fois 2 fois 1. Et 4 factorielle est 4 fois 3 fois 2 fois 1 et ainsi de suite. Vous avez l'idée. 

Comme les programmeurs, nous ne faisons pas utiliser n, point d'exclamation. Donc, nous allons définir la factorielle fonction comme un fait de n. Et nous allons utiliser pour créer factorielle une solution à un problème récurrent. Et je pense que vous pourriez trouver qu'il est beaucoup plus visuelle appel que la itérative version de ce qui nous allons aussi jeter un oeil à dans un moment. 

Donc, voici un couple de calembour facts-- intended-- factorial-- sur la fonction factorielle. La factorielle de 1, comme je le disais, est 1. La factorielle de 2 est 2 fois 1. La factorielle de 3 est 3 1 fois et 2 fois, et ainsi de suite. Nous avons parlé de 4 et 5 déjà. 

Mais en regardant cela, est-ce pas vrai? Est pas factorielle de 2 seulement 2 fois la factorielle de 1? Je veux dire, la factorielle de 1 est 1. Alors pourquoi ne pouvons-nous pas tout simplement dire que, depuis factorielle de 2 est 2 fois 1, il est vraiment juste 2 fois la factorielle de 1? 

Et puis, étendant cette idée, est pas la factorielle de 3 seulement 3 fois la factorielle de 2? Et la factorielle de 4 est 4 fois la factorielle de 3, et ainsi de suite? En fait, la factorielle d'un nombre quelconque peut juste être exprimé si nous type de porter ce pour toujours. Nous pouvons sorte de généraliser le problème factorielle car il est n fois les factorielle de n moins 1. Il est n fois le produit de tous les nombres inférieurs à moi. 

Cette idée, cette généralisation du problème, nous permet de façon récursive définir la fonction factorielle. Lorsque vous définissez une fonction récursive, il ya deux choses qui doivent être une partie de celui-ci. Vous avez besoin d'avoir quelque chose appelé un scénario de base, qui, lorsque vous déclenchez ce, va arrêter le processus récursif. 

Sinon, une fonction qui appelle itself-- que vous pourriez imagine-- pourrait durer éternellement. Appelle la fonction appelle les appels de fonction la fonction appelle la fonction. Si vous ne disposez pas d'une manière pour l'arrêter, votre programme seront effectivement coincé à une boucle infinie. Il va se planter finalement, parce que ça va manquer de mémoire. Mais que ce côté de la question. 

Nous avons besoin d'un autre moyen d'arrêter choses encore notre plantage du programme, car un programme qui plante est probablement pas beau ou élégant. Et si nous appelons cela le cas de base. Ceci est une solution simple à un problème qui stoppe le processus récursif de se produire. Voilà donc une partie de une fonction récursive. 

La deuxième partie est le cas récursif. Et cela est l'endroit où la récursion aura effectivement lieu. Ceci est où le fonction appeler lui-même. 

Il ne sera pas appeler lui-même exactement de la même manière qu'il a été appelé. Ça va être une légère variation qui rend le problème il est essayer de résoudre un tout petit peu plus petit. Mais il passe généralement le mâle la résolution de la masse de la solution à un autre appel sur la ligne. 

Lequel de ces regards comme dans le cas de base ici? Lequel de ces regards comme le solution la plus simple à un problème? Nous avons un tas de factorielles, et nous pourrions continuer aller on-- 6, 7, 8, 9, 10, et ainsi de suite. 

Mais un de ces regards comme un bon exemple est le cas de base. Il est une solution très simple. Nous ne disposons pas de faire quelque chose de spécial. 

La factorielle de 1 est juste 1. Nous ne devons pas faire de la multiplication du tout. Il semble que si nous allons pour essayer de résoudre ce problème, et nous devons arrêter la récursivité quelque part, nous voulons probablement arrêter quand nous arrivons à 1. Nous ne voulons pas arrêter avant que. 

Donc, si nous définissons notre fonction factorielle, voici un squelette pour comment nous pourrions le faire. Nous avons besoin de brancher ces deux things-- le cas de base et le cas récursif. Quel est le scénario de base? Si n est égal à 1, revenir 1-- qui est un problème très simple à résoudre. 

La factorielle de 1 est 1. Ce ne sont pas 1 fois rien. Il est juste 1. Il est un fait très facile. Et si cela peut être notre scénario de base. Si nous sommes passés dans ce 1 fonction, nous allons simplement revenir 1. 

Quel est le récursif cas probablement ressembler? Pour tout autre nombre Outre 1, ce qui est le motif? Eh bien, si nous prenons la factorielle de n, Il est n fois la factorielle de n moins 1. 

Si nous prenons la factorielle de 3, il est 3 fois la factorielle de 3 moins 1, ou deux. Et si nous ne sommes pas regardant 1, sinon retour n fois les factorielle de n moins 1. Il est assez simple. 

Et pour le plaisir d'avoir légèrement plus propre et plus de code élégant, savoir que si nous avons des boucles seule ligne ou une seule ligne de branches conditionnelles, nous pouvons nous débarrasser de tous les accolades autour d'eux. Donc, nous pouvons consolider ce à cela. Ceci a exactement la même fonctionnalité que cette. 

Je suis juste enlever l'bouclés accolades, car il n'y a qu'une seule ligne à l'intérieur de ces branches conditionnelles. Donc, ce comportement identique. Si n est égal à 1, renvoie 1. Sinon retourner n fois la factorielle de n moins 1. Nous allons donc faire le plus petit problème. Si n commence comme 5, nous allons revenir 5 fois la factorielle de 4. Et nous verrons dans un instant lorsque nous parlons sur le stack-- d'appel dans une autre vidéo où nous parlons de la appeler stack-- nous apprendrons à propos de pourquoi exactement ce processus fonctionne. 

Mais tandis que factorielle de 5 dit revenir 5 fois factorielle de 4, et 4 va dire, OK, bien, le retour 4 fois la factorielle de 3. Et comme vous pouvez le voir, nous sommes sorte d'approche 1. Nous nous rapprochons et plus proche de celle cas de base. 

Et une fois que nous avons touché le cas de base, l'ensemble des fonctions précédentes avoir la réponse qu'ils cherchaient. Factorielle de 2 disait retour 2 fois la factorielle de 1. Eh bien, factorielle de 1 renvoie 1. Donc, l'appel à factoriel 2 peut retourner 2 fois 1, et donner ce retour à factorielle 3, qui est en attente pour ce résultat. 

Et puis, il peut calculer son résultat, 3 fois 2 est 6, et le remettre à factorielle de 4. Et encore une fois, nous avons une vidéo sur la pile d'appel où cela est illustré un peu plus que ce que je dis en ce moment. Mais ce qu'il est. Cela seul est la solution à le calcul de la factorielle d'un nombre. 

Il est seulement quatre lignes de code. Cela est plutôt cool, non? Il est un peu sexy. 

Donc, en général, mais pas toujours, une fonction récursive peut remplacer une boucle dans un fonction non récursive. Donc, ici, côte à côte, est la itérative version de la fonction factorielle. Ces deux Calculer exactement la même chose. 

Ils ont tous deux calculer la factorielle de n. La version sur la gauche utilise la récursivité pour le faire. La version sur la droite utilise itération de le faire. 

Et remarquez, nous avons à déclarer une variable d'un produit entier. Et puis on boucle. Tant que n est supérieur à 0, on garder multipliant ce produit par n et la décrémentation de n jusqu'à ce que nous calculons le produit. Donc, ces deux fonctions, à nouveau, faire exactement la même chose. Mais ils ne le font pas dans exactement de la même façon. 

Maintenant, il est possible de avoir plus d'une base cas ou plus d'un cas récursif, selon sur ce que votre fonction essaie de faire. Vous n'êtes pas nécessairement juste limité à un cas de base ou un seul récursive cas. Donc, un exemple de quelque chose avec des cas de base multiples pourrait être l'this-- Séquence de nombres de Fibonacci. 

Vous vous souvenez peut partir jours de l'école élémentaire que la suite de Fibonacci est définie comme this-- le premier élément est 0. Le deuxième élément est une. Les deux sont tout simplement par définition. 

Puis tout autre élément est défini que la somme de n et n moins 1 moins 2. Ainsi, le troisième élément serait 0 + 1 est 1. Et puis le quatrième élément serait le deuxième élément, 1, ainsi que le troisième élément, une. Et ce serait 2. Ainsi de suite. 

Donc dans ce cas, nous avons deux cas de base. Si n est égal à 1, retourner 0. Si n est égal à 2, retourner 1. Sinon, le retour de Fibonacci de n moins 1 plus de Fibonacci de n moins 2. 

Voilà donc les cas de plusieurs bases. Qu'en est-il des cas multiples récursives? Eh bien, il ya quelque chose appelé la conjecture de Syracuse. Je ne vais pas dire, vous savez ce qui est, car il est en fait notre dernière problème pour cette vidéo notamment. Et il est de notre exercice de travailler ensemble. 

Alors, voici ce que le Collatz Conjecture est-- il applique à chaque nombre entier positif. Et il spécule qu'il est toujours possible de revenir 1 si vous suivez ces étapes. Si n est 1, arrêter. Nous avons de retour à 1 si n est 1. 

Sinon, passez à travers cette processus nouveau sur n divisé par 2. Et voir si vous pouvez revenir à 1. Sinon, si n est impair, passer par ce processus nouveau sur 3n + 1, ou 3 fois n plus 1. Nous avons donc ici un cas de base unique. Si n est égal à 1, arrêter. Nous ne faisons plus la récursivité. 

Mais nous avons deux cas récursives. Si n est pair, nous faisons un récursif cas, appelant n divisé par 2. Si n est impair, nous faisons un autre récursif cas sur 3 fois n + 1. 

Et donc le but de cette vidéo est de prendre une seconde, pause de la vidéo, et essayer d'écrire ce fonction récursive Collatz où vous passez une valeur n, et il calcule le nombre de mesures qu'il faut pour arriver à 1 si vous commencez à partir de n et vous suivez ces étapes au-dessus. Si n est égal à 1, il faut 0 étapes. Sinon, ça va faire un pas en plus mais de nombreuses mesures qu'il prend sur soit n divisée par 2 si n est pair, ou 3n + 1 si n est impair. 

Maintenant, je l'ai mis en place sur l'écran ici un couple de tester des choses pour vous, un couple de cas de tests pour vous, pour voir ce que ces divers nombres sont Collatz, et également une illustration les étapes de besoin d'être traversé afin que vous puissiez sorte de voir ce processus en action. Donc, si n est égal à 1, Collatz de n est 0. Vous ne devez pas faire quoi que ce soit pour revenir à 1. Vous y êtes déjà. 

Si n est égal à 2, il faut une étape pour arriver à 1. Vous commencez avec 2. Eh bien, pas 2 est égal à 1. Donc, ça va être une étape Cependant, plus de nombreuses mesures qu'il prend n divisé par 2. 

2 divisé par 2 est une. Il faut donc une étape en plus cependant de nombreuses étapes qu'il faut pour 1. 1 prend zéro étapes. 

Pour 3, comme vous pouvez le voir, il ya tout à fait à quelques pas impliqués. Vous allez de 3. Et puis vous allez à 10, 5, 16, 8, 4, 2, 1. Il faut sept étapes pour revenir à 1. Et comme vous pouvez le voir, il ya une quelques autres cas de test ici pour tester votre programme. Donc encore une fois, mettre en pause la vidéo. Et je vais revenir en arrière maintenant ce que le processus réel est ici, ce que cette conjecture est. 

Voyez si vous pouvez comprendre comment définir Collatz de n de sorte qu'il calcule combien les étapes qu'il faut pour arriver à 1. Donc, je l'espère, vous avez suspendu la vidéo et vous n'êtes pas simplement en attente pour moi pour vous donner la réponse ici. Mais si vous êtes, ainsi, voici la réponse de toute façon. 

Alors, voici une définition possible de la fonction Collatz. Notre base case-- si n est égale à 1, nous revenons 0. Il ne prend pas des mesures pour revenir à 1. 

Sinon, nous avons deux cases-- récursive un pour les nombres pairs et un pour impair. La façon dont je test pour les nombres pairs est de vérifier si n mod 2 est égal à 0. Ceci est essentiellement, à nouveau, poser la question, si vous vous souvenez est-- ce mod si je fracture n par 2 est-il pas de reste? Ce serait un nombre pair. 

Et donc, si n est égal à 0 mod 2 est test est-ce un nombre pair. Si oui, je veux revenir 1, parce que cela est certainement faire un pas en plus de Collatz peu importe le nombre est la moitié de moi. Sinon, je veux revenir 1 ainsi Collatz de 3 fois n plus 1. Ce fut l'autre étape récursive qui nous pourrait prendre pour calculer la Collatz-- le nombre d'étapes il faut revenir à 1 donné un numéro. Donc, je l'espère, cet exemple vous a donné un peu d'un goût de procédures récursives. Heureusement, vous pensez que le code est un peu plus belle si elle est appliquée dans un élégant, de manière récursive. Mais même si pas, la récursivité est un vraiment puissant outil néanmoins. Et il est certainement quelque chose pour obtenir votre tête autour, parce que vous serez en mesure de créer programmes assez cool en utilisant la récursivité qui pourraient autrement être complexe à écrire si vous utilisez des boucles et itération. Je suis Doug Lloyd. Ceci est CS50.