ZAMYLA: Per tal d'entendre recursivitat, s'ha de primer entendre la recursivitat. Tenir la recursivitat en el programa de disseny de mitjans que té autoreferencial definicions. Estructures de dades recursives, per exemple, són estructures de dades que incloure a si mateixos en les seves definicions. Però avui en dia, ens centrarem en funcions recursives. 

Recordem que les funcions necessiten entrades, arguments i retorna un valor com el seu de sortida representat per aquest diagrama aquí. Ja pensarem en la caixa com el cos de la funció, que conté el conjunt de instruccions que interpreten el d'entrada i proporcionar una sortida. Prenent una mirada més propera a l'interior del cos de la funció podria revelar les trucades a altres funcions també. Prengui aquesta funció simple, foo, que pren una sola cadena com a entrada i impressions de quantes lletres aquesta cadena té. El strlen funció, per longitud de la cadena, es diu, la sortida és requerit per la crida a printf. 

Ara, el que fa una funció recursiva especial és que es diu a si mateixa. Podem representar aquest recursiva trucar amb aquesta fletxa taronja bucle de nou a si mateix. Però l'execució en si de nou només es realitzar una altra crida recursiva, i altre i un altre. Però les funcions recursives no pot ser infinit. Han d'acabar d'alguna manera, o si programa s'executarà sempre. 

Així que hem de trobar una manera de trencar de les crides recursives. D'això en diem el cas base. Quan es compleix la condició de cas base, la funció retorna sense fer una altra crida recursiva. Prengui aquesta funció, hi, una funció void que pren un sencer n com a entrada. El cas base és el primer. Si n és menor que zero, adéu d'impressió i tornar Per a tots els altres casos, el funció imprimirà hi i executar la crida recursiva. Una altra crida a la funció amb hi un valor d'entrada decrementa. 

Ara, tot i que imprimim hi, la funció no acabarà fins que retornar el seu tipus de retorn, en aquest cas sense efecte. Així, per cada n que no sigui el cas base, aquesta funció hi hi tornarà de n almenys 1. Atès que aquesta funció no és vàlida, però, que no s'escrigui explícitament retorn aquí. Acabàvem executarem la funció. Així de trucar hi (3) imprimirà hola i executar hi (2), que executa hi (1) un que executa hi (0), en què el es compleix la condició de cas base. Així hi (0) imprimeix bye i torna. 

D'acord. Així que ara que entenem els fonaments de la funcions recursives, que necessiten almenys un cas base, així com un crida recursiva, anem a passar a un exemple més significatiu. Un que no només tornar anul · lar tant i fa. 

Anem a fer una ullada a el factorial operació més comunament utilitzat en càlculs de probabilitat. Factorial d'n és el producte de tots els nombre enter positiu menys i igual a n. Així que 5 factorial és 5 vegades 4 vegades 3 vegades 2 cops 1 per a donar 120. Quatre factorial és 4 vegades 3 vegades 2 cops 1 per a donar 24. I s'aplica la mateixa regla a qualsevol nombre enter positiu. 

Llavors, com podríem escriure una recursiva funció que calcula el factorial d'un nombre? Bé, anem a necessitar per identificar tant el cas base i la crida recursiva. La crida recursiva serà el mateix per a tots els casos excepte per a la base cas, el que significa que haurem de trobar un patró que ens donarà la nostra resultat desitjat. 

Per a aquest exemple, veure com 5 factorial implica multiplicar 4 per 3 per 2 per 1 I aquesta mateixa multiplicació es troba aquí, el definició de 4 factorial. Així que veiem que 5 factorial és a 5 vegades 4 factorial. Ara s'aplica aquest patró a 4 factorial, així? Sí Veiem que 4 factorial conté la multiplicar 3 vegades 2 cops 1, el pròpia definició com 3 factorial. Així factorial 4 és igual a 4 vegades 3 factorial, i així successivament i així successivament nostra patró de pals fins a 1 factorial, la qual per definició és igual a 1. 

No hi ha altra positiva sencers van ser. Així que tenim el model per nostra crida recursiva. n factorial és igual a n vegades el factorial de n almenys 1. I el nostre cas base? Això acaba de ser la nostra definició d'1 factorial. 

Així que ara podem passar a l'escriptura codi de la funció. Per al cas base, que tindrem la condició n és igual a és igual a 1, en els quals li retornarem 1. Després de passar a la crida recursiva, tornarem n vegades el factorial de n almenys 1. 

Ara anem a provar aquesta nostra. Provem factorial 4. Per la nostra funció és igual a 4 vegades factorial (3). Factorial (3) és igual a 3 vegades factorials (2). Factorial (2) és igual a 2 vegades factorial (1), que retorna 1. Factorial (2) ara retorna 2 temps 1, 2. Factorial (3) ara pot tornar 3 vegades 2, 6. I, finalment, factorial (4) retorna 4 temps 6, 24. 

Si vostè està trobant alguna dificultat amb la crida recursiva, pretendre que la funció ja funciona. El que vull dir amb això és que vostè ha confiar en les seves trucades recursives per tornar els valors correctes. Per exemple, si jo sé que factorial (5) és igual a 5 vegades factorial (4), vaig a confiar que factorial (4) em donarà 24. Penseu en això com una variable, si voluntat, com si ja ha definit factorial (4). Així que per a qualsevol factorial (N), que és el producte de n i el factorial anterior. I això factorial anterior s'obté trucant al factorial de n almenys 1. 

Ara, a veure si es pot implementar un recursiva funcionar a tu mateix. Càrrega teu terminal, o run.cs50.net, i escriure una funció sum que pren un sencer n i retorna el suma de totes positiva consecutiva nombres enters de n és 1. He escrit una ullada a les sumes d'alguns valors que l'ajudaran a la nostra. En primer lloc, esbrinar el condicions del cas base. Llavors, mira suma (5). Es pot expressar en termes d'una altra suma? Ara, què passa amb summa (4)? Com es pot expressar suma (4) en termes d'una altra suma? 

Un cop tingueu suma (5) i suma (4) expressat en termes d'altres quantitats, consulteu si es pot identificar una patró per la suma (n). Si no, proveu alguns altres números i expressar les seves sumes en termes d'altres números. Mitjançant la identificació dels patrons de discreta números, vostè està bé en la seva manera de identificar el patró per a qualsevol n. 

La recursivitat és una eina molt poderosa, així que per descomptat no es limita a funcions matemàtiques. La recursivitat pot ser utilitzat de manera molt eficaç quan es tracta d'arbres, per exemple. Fes una ullada a la tallada dels arbres durant un opinió més a fons, però per ara recordar que els arbres de cerca binaris, en en particular, es componen de nodes, cadascun amb un valor i dos punters de node. En general, això està representat pel node pare té una apuntant línia al node fill esquerre i un al node fill dret. L'estructura d'una recerca binària arbre es presta bé a una recerca recursiva. L'anomenada recursiva sigui passa al esquerra o dreta en el node, però més que en el curt arbre. 

Diguem que vostè vol fer una operació en cada node individual en un arbre binari. Com podria vostè anar sobre això? Bé, es podria escriure un recursiu la funció que realitza l'operació en el node pare i fa una recursiva cridar a la mateixa funció, que passa a l'esquerra i nodes secundaris adequats. Per exemple, aquesta funció, foo, que canvia el valor d'un node donat i tots els seus fills a la 1. El cas base d'un node causes nuls la funció per tornar, el que indica que no hi ha nodes deixat en aquest sub-arbre. 

Anem a caminar a través d'ell. El primer dels pares és de 13. Canviem el valor a 1, i després diem la nostra funció a la banda esquerra, així com el dret. La funció, foo, es diu a l'esquerra sub-arbre en primer lloc, de manera que el node esquerre serà reassignat a 1 i Foo es va demanar als nens d'aquest node, primer l'esquerra i després la dreta, i així successivament i així successivament. I els dic que les branques no tenen tenir més fills de manera que el mateix procés continuarà pels fills dreta fins als nodes de la totalitat dels arbres són reassignat a 1. 

Com podeu veure, vostè no està limitat a només una crida recursiva. Igual que tots els que aconseguirà la feina feta. Què passa si vostè tenia un arbre on cada node va tenir tres fills, Esquerra, Centre i Dreta? Com editar foo? Bé, simple. Només ha d'afegir una altra crida recursiva i passi el punter del node intermedi. 

La recursivitat és molt potent i no esmenta elegant, però pot ser un difícil concepte al principi, així que pacient i prengui el seu temps. Comenceu amb el cas base. En general és la més fàcil d'identificar, i llavors vostè pot treballar cap enrere des d'allà. Vostè sap que necessita per arribar al seu cas base, de manera que el poder donar-li alguns consells. Intenta expressar un cas específic en termes d'altres causes o en sub-conjunts. 

Gràcies per veure aquest curt. Si més no, ara pot fer-ho entendre acudits com aquest. El meu nom és Zamyla, i això és CS50. 

Prengui aquesta funció, hi un void funció que pren 01:00 int, n, com a entrada. El cas base és el primer. Si n és menor que 0, imprimir "Bye" i el retorn.