ZAMYLA: Afin de comprendre récursivité, vous devez d'abord comprendre la récursivité. Avoir la récursivité dans les moyens de la conception du programme que vous avez auto-référentielle définitions. Structures de données récursives, par exemple, sont des structures de données qui se inclure dans leurs définitions. Mais aujourd'hui, nous allons nous concentrer sur les fonctions récursives. 

Rappelons que les fonctions prennent entrées, arguments, et retourner une valeur comme sortie représentée par ce schéma ici. Nous pensons de la boîte que le corps de la fonction, qui contient l'ensemble d' instructions qui interprètent la entrée et fournir un signal de sortie. Regardons de plus près l'intérieur du corps de la fonction pourrait révéler des appels à d'autres fonctions ainsi. Prenez cette simple fonction, foo, que prend une seule chaîne en entrée et gravures combien de lettres cette chaîne a. La fonction strlen, pour la longueur de chaîne, est appelée, dont la sortie est requis pour l'appel à printf. 

Maintenant, ce qui rend une fonction récursive spécial, c'est qu'il appelle lui-même. Nous pouvons représenter cette récursive appeler avec cette flèche orange boucle sur lui-même. Mais lui-même l'exécution de nouveau ne fera que faire un autre appel récursif, et autre et un autre. Mais les fonctions récursives ne peut pas être infinie. Ils doivent finir en quelque sorte, ou votre programme fonctionnera toujours. 

Nous devons donc trouver un moyen de briser sur les appels récursifs. Nous appelons cela le cas de base. Lorsque l'état de cas de base est atteint, la fonction retourne sans faire un autre appel récursif. Prenez cette fonction, salut, une fonction de vide qui prend un int n en entrée. Le cas de base vient en premier. Si n est inférieur à zéro, l'impression et au revoir retourner tous les autres cas, la fonction imprimer salut et exécuter l'appel récursif. Un autre appel à la fonction salut avec une valeur d'entrée décrémenté. 

Maintenant, même si nous imprimons salut, l' fonction ne mettra pas fin jusqu'à ce que nous retourner son type de retour, dans ce cas, nul. Ainsi, pour chaque n autre que le cas de base, cette fonction retournera salut salut de n moins 1. Comme cette fonction est nulle si, nous ne sera pas explicitement le type de retour ici. Nous allons exécuter la fonction. Donc, appeler salut (3) permet d'imprimer salut et exécuter salut (2) qui exécute salut (1) un qui exécute salut (0), où l' cas de base condition est remplie. Alors salut (0) imprime au revoir et retours. 

OK. Alors, maintenant que nous comprenons les bases de fonctions récursives, dont ils ont besoin au moins un cas de base, ainsi qu'un appel récursif, passons à un exemple plus significatif. Un qui ne se retourne pas annuler n'importe quoi. 

Jetons un coup d'oeil à la factorielle fonctionnement utilisé le plus souvent dans calculs de probabilité. Factorielle de n est le produit de tous les nombre entier positif inférieur à et égal à n. Donc cinq factorielle est 5 fois 4 fois 3 fois 2 fois 1 pour donner 120. Quatre factorielle est 4 fois 3 fois 2 fois 1 pour donner 24. Et la même règle s'applique à n'importe quel nombre entier positif. 

Alors, comment pourrions-nous écrire un récursive fonction qui calcule la factorielle d'un certain nombre? Eh bien, nous avons besoin d'identifier le cas de base et l'appel récursif. L'appel récursif sera la même dans tous les cas à l'exception de la base cas, ce qui signifie que nous devrons trouver un modèle qui nous donnera notre résultat souhaité. 

Pour cet exemple, voir comment 5 factorielle consiste à multiplier 4 par 3 par 2 par 1 Et cette même multiplication se trouve ici, l' définition de quatre factorielle. Nous voyons donc que 5 factorielle est seulement 5 fois 4 factorielle. Maintenant pas cette tendance à 4 factorielle ainsi? Oui. Nous voyons que 4 factorielle contient le multiplication 3 fois 2 fois 1, la même définition que 3 factorielle. Donc 4 factorielle est égale à 4 fois 3 factorielle, et ainsi de suite et ainsi de suite notre modèle colle jusqu'à une factorielle, qui par définition, est égal à 1. 

Il n'y a pas d'autre positif entiers laissés. Nous avons donc le modèle pour notre appel récursif. n le facteur est égal à n fois la factorielle de n moins 1. Et notre scénario de base? Ce sera juste notre définition de 1 factorielle. 

Alors maintenant, nous pouvons passer à l'écriture code de la fonction. Pour le cas de base, nous avons la état n est égal à égal à 1, où nous reviendrons 1. Puis passer à l'appel récursif, nous reviendrons n fois la factorielle de n moins 1. 

Testons maintenant ce notre. Essayons factorielle 4. Par notre fonction c'est égal à 4 fois par factorielle (3). Factorielle (3) est égal à 3 fois factoriels (2). Factorielle (2) est égale à 2 fois factorielle (1), qui renvoie 1. Factorielle (2) renvoie maintenant 2 fois 1, 2. Factorielle (3) peut maintenant revenir 3 fois 2, 6. Et enfin, factorielle (4) retourne 4 fois 6, 24. 

Si vous rencontrez des difficultés avec l'appel récursif, prétendre que la fonction fonctionne déjà. Ce que je veux dire par là que vous devriez faites confiance à vos appels récursifs à revenir les bonnes valeurs. Par exemple, si je sais que factorielle (5) est égale à 5 fois factorielle (4), je vais faire confiance à cette factorielle (4) va me donner 24. Pensez-y comme une variable, si vous volonté, comme si vous avez déjà défini factorielle (4). Donc pour tout factorielle (n), c'est le produit de n et la factorielle précédente. Et ce factorielle précédente est obtenu en appelant factorielle de n moins 1. 

Maintenant, voyez si vous pouvez mettre en œuvre une récursive fonctionner vous-même. Chargez votre terminal, ou run.cs50.net, et écrire une fonction somme qui prend un entier n et renvoie le somme de tous positifs consécutive entiers de n à 1. J'ai écrit les sommes d'une certaine valeurs pour vous aider notre. Tout d'abord, comprendre la cas de base état. Ensuite, regardez somme (5). Pouvez-vous exprimer en termes d'une autre somme? Maintenant, qu'en est-il somme (4)? Comment pouvez-vous exprimer somme (4) en termes d'une autre somme? 

Une fois que vous avez somme (5) et la somme (4) exprimé en d'autres sommes, voir si vous pouvez identifier un modèle pour la somme (n). Si non, essayez quelques autres numéros et d'exprimer leurs sommes en termes d'un autre nombre. En identifiant les modèles de discret numéros, vous êtes bien sur votre chemin à identifier le modèle pour tout n. 

La récursivité est un outil très puissant, alors bien sûr il n'est pas limité à des fonctions mathématiques. Récursivité peut être utilisé très efficacement lorsqu'il s'agit d'arbres par exemple. Découvrez le court sur les arbres pour une plus approfondis, mais pour l'instant rappeler que les arbres binaires de recherche, en particulier, sont constitués de nœuds, chaque avec une valeur et deux pointeurs de noeuds. Habituellement, ceci est représenté par l' nœud parent ayant un pointage de ligne au noeud enfant gauche et une au noeud de droit de l'enfant. La structure d'une recherche binaire arbre se prête bien à une recherche récursive. L'appel récursif passe soit dans la gauche ou la droite noeud, mais plus de celle de l'arbre court. 

Dites que vous voulez effectuer une opération sur chaque nœud unique dans un arbre binaire. Comment pourriez-vous aller à ce sujet? Eh bien, vous pourriez écrire un récursive fonction qui effectue l'opération sur le noeud parent et fait un récursive appeler à la même fonction, passant à gauche et à nœuds enfants droite. Par exemple, cette fonction, foo, que modifie la valeur d'un noeud donné et tous ses enfants à 1. Le cas de base d'une valeur NULL causes nœud la fonction de retour, indiquant qu'il n'y a pas de noeuds laissé dans ce sous-arbre. 

Marchons à travers elle. Le premier parent est de 13. Nous changeons la valeur à 1, puis appelons notre fonction sur la gauche ainsi que le droit. La fonction foo est appelée sur la gauche sous-arbre d'abord, si le nœud gauche seront réaffectés à 1 et foo être appelée sur les enfants de ce nœud, d'abord la gauche, puis le droit, et ainsi de suite et ainsi de suite. Et leur dire que les branches n'ont pas tout plus d'enfants si le même processus continuera pour les droit de l'enfant jusqu'à ce que les noeuds de l'arbre entier sont réaffecté à 1. 

Comme vous pouvez le voir, vous n'êtes pas limité juste un appel récursif. Tout autant que va faire le travail. Et si vous aviez un arbre où chaque noeud a eu trois enfants, Gauche, au milieu, et à droite? Comment pourriez-vous modifier foo? Eh bien, simple. Il suffit d'ajouter un autre appel récursif et passer le pointeur de la médiane. 

La récursivité est très puissant et ne pas mentionne élégant, mais il peut être un concept difficile au premier abord, alors patient et prenez votre temps. Commencez par le cas de base. Il est généralement plus facile à identifier, et alors vous pouvez travailler arrière à partir de là. Vous savez que vous devez atteindre votre cas de base, de sorte que la puissance vous donner quelques conseils. Essayez d'exprimer un cas spécifique, Quant aux autres cas, ou dans des sous-ensembles. 

Merci pour regarder ce court. À tout le moins, maintenant vous pouvez comprendre les blagues de ce genre. Mon nom est Zamyla, et c'est CS50. 

Prenez cette fonction, salut, un fonction vide qui prend un int, n, comme entrée. Le cas de base vient en premier. Si n est inférieur à 0, imprimer "Bye" et retour.