[REPRODUCCIÓ DE MÚSICA] 

DOUG LLOYD: Vostè probablement pensa que codi només s'utilitza per a realitzar una tasca. Vostè escriu a terme. Fa alguna cosa. Això és més o menys la mateixa. 

Vostè compilar-lo. Executa el programa. Vostè està bo per anar. 

Però ho creguis o no, si codificar per un llarg temps, en realitat es pot arribar a veure codi com una cosa que és bonic. Soluciona un problema en una forma molt interessant, o hi ha alguna cosa de veritat endreçada sobre la forma en què es veu. Vostè podria estar rient a mi, però és la veritat. I recursivitat és una forma per aconseguir una espècie d'aquesta idea de la bella, d'aspecte elegant codi. Soluciona problemes de manera que són interessants, fàcil de visualitzar, i sorprenentment curt. 

Les obres manera recursivitat és, una funció recursiva es defineix com una funció que crida a si mateixa com a part de la seva execució. Això pot semblar una mica estrany, i anem a veure una mica sobre com funciona això en un moment. Però, de nou, aquests procediments recursius són serà tan elegant perquè van per resoldre aquest problema sense tenint totes aquestes altres funcions o aquests llargs bucles. Vas a veure que aquests recursiva procediments van a semblar tan curt. I realment es va a fer el seu codi semblen molt més bonica. 

Et vaig a donar un exemple d'això per veure com un procediment recursiu pot definir-se. Així que si vostè està familiaritzat amb aquest de la classe de matemàtiques, fa molts anys, Hi ha alguna cosa cridat el funció factorial, que és generalment denotat com un signe d'exclamació, que es defineix sobre tots els enters positius. I la forma en què n factorial es calcula està vostè multiplica tots els números de menys de o igual a n junts-- tots els números sencers de menys de o igual a n junts. 

Així maig factorial és 5 vegades 4 vegades 3 vegades 2 vegades 1. I 4 factorial és 4 vegades 3 vegades 2 cops 1 i així successivament. Vostè aconsegueix la idea. 

Com programadors, no ho fem utilitzar n, signe d'exclamació. Així que anem a definir el factorial funció com un fet de n. I utilitzarem factorial per crear una solució recursiva a un problema. I crec que podria trobar que és molt més visual apel·lant a la iterativa versió d'aquest, el qual també anem a fer una ullada a en un moment. 

Així que aquí hi ha un parell de joc de paraules facts-- intended-- sobre la factorial-- funció factorial. El factorial d'1, com ja he dit, és 1. El factorial de 2 és 2 vegades 1. El factorial de 3 és 3 Temps 2 Temps 1, i així successivament. Parlem de 4 i 5 ja. 

Però en mirar a això, no és això cert? ¿No és el factorial de 2 només 2 vegades el factorial d'1? Vull dir, el factorial d'1 es 1. Per què no podem simplement dir que, des factorial de 2 és 2 vegades 1, és realment només 2 vegades el factorial d'1? 

I després estendre aquesta idea, no és el factorial de 3 només 3 vegades el factorial de 2? I el factorial de 4 és 4 vegades el factorial de 3, i així successivament? De fet, el factorial de qualsevol nombre pot simplement ser expressada si espècie de portar això a terme sempre. Podem tipus de generalitzar el problema factorial ja que és n vegades els factorial de n almenys 1. És n vegades el producte de tots els nombres menors que jo. 

Aquesta idea, això generalització del problema, ens permet de forma recursiva definir la funció factorial. Quan es defineix una funció recursiva, hi ha dues coses que han de ser part d'ella. Vostè necessita tenir una cosa anomenada cas base, que, quan vostè els activa, s'aturarà el procés recursiu. 

Altrament, una funció que crida itself-- com es podria imagine-- podria continuar per sempre. Funció crida a la funció crida a les trucades de funció la funció crida a la funció. Si vostè no té una forma per detenir-lo, el seu programa serà atrapat amb eficàcia en un bucle infinit. Serà estavellar finalment, perquè es quedarà sense memòria. Però això no ve al cas. 

Hem de tenir alguna altra manera d'aturar coses a més del nostre programa de estavellar-se, perquè un programa que s'estavella és Probablement no és bell o elegant. I així en diem el cas base. Aquesta és una solució simple a un problema que s'atura el procés recursiu que es produeixin. Així que aquesta és una part de una funció recursiva. 

La segona part és el cas recursiu. I aquí és on la recursivitat en realitat tenir lloc. Aquí és on el funció es digui a si mateix. 

No va a dir-exactament de la mateixa manera que es deia. Serà una lleugera variació que fa que el problema és tractant de resoldre una miqueta més petit. Però en general, passa la pilota de resoldre la major part de la solució a una trucada diferent en la línia. 

Quin d'aquests looks com el cas base en aquesta llista? Quin d'aquests looks com el solució més senzilla a un problema? Tenim un munt de factorials, i podríem continuar anar en-- 6, 7, 8, 9, 10, i així successivament. 

Però un d'aquests sembla un bon cas és el cas base. És una solució molt simple. No hem de fer res especial. 

El factorial d'1 es 1. No hem de fer cap multiplicació en absolut. Sembla com si anem per tractar de resoldre aquest problema, i hem d'aturar la recursivitat en algun lloc, probablement volem aturar quan vam arribar a 1. No volem que s'aturi abans d'això. 

Així que si estem definint la nostra funció factorial, aquí està un esquelet per com podem fer això. Hem de connectar aquests dos coses-- el cas base i el cas recursiu. Quin és el cas base? Si n és igual a 1, tornar 1-- això és un problema molt simple de resoldre. 

El factorial d'1 es 1. No són 1 vegades res. És només 1. És un fet molt fàcil. I perquè pugui ser el nostre cas base. Si ens passem 1 en aquest funció, només haurem de tornem gener. 

Quina és la recursiva cas probablement sembla? Per cada altre número a més d'1, quin és el patró? Bé, si estem prenent el factorial de n, És en moments n el factorial de n almenys 1. 

Si estem prenent el factorial de 3, que és 3 vegades el factorial de 3 menys 1, o 2. I pel que si no estem mirant a 1, en cas contrari retorn n vegades els factorial de n almenys 1. És bastant senzill. 

I pel bé de tenir una mica més neta i més elegant de codi, saber que si tenim bucles d'una sola línia o d'una sola línia de salts condicionals, podem desfer-nos de tota la claus al voltant d'ells. Així que podem consolidar aquest a això. Això té exactament el mateix funcionalitat que això. 

Només estic traient l'arrissat suports, perquè només hi ha una línia dins d'aquestes branques condicionals. Així que aquests es comporten de forma idèntica. Si n és igual a 1, tornar 1. Altrament tornarà n vegades el factorial de n almenys 1. Així que estem fent el problema més petit. Si n comença com 5, anem a tornar 5 vegades el factorial de 4. I veurem en un minut quan parlem sobre la stack-- anomenada en un altre vídeo on es parla de la cridar stack-- aprendrem sobre per què exactament aquest procés funciona. 

Però mentre factorial de 5 diu tornar 5 vegades factorial de 4, i 4 es dirà, bé, bé, el retorn 4 vegades el factorial de 3. I com es pot veure, estem tipus d'apropar a 1. Estem cada vegada més a prop i més propera a la del cas base. 

I una vegada que arribem a la hipòtesi de base, totes les funcions anteriors tenir la resposta que estaven buscant. Factorial de 2 estava dient retorn 2 vegades el factorial d'1. Bé, factorial d'1 torna 1. Així que la convocatòria de factorial de 2 pot tornar 2 cops 1, i donar aquesta volta a factorial de 3, que està a l'espera d'aquest resultat. 

I llavors es pot calcular el seu resultat, 3 vegades 2 és 6, i donar-li volta a factorial de 4. I de nou, tenim una vídeo a la pila de trucades on això s'il·lustra una mica més del que estic dient ara. Però això és tot. Això per si sol és la solució a calcular el factorial d'un nombre. 

És només quatre línies de codi. Això està molt bé, oi? És una mica sexy. 

Així que en general, però no sempre, una funció recursiva pot substituir un bucle en una funció no recursiva. Així que aquí, al costat de l'altre, és el iteratiu versió de la funció factorial. Tots dos calcular exactament el mateix. 

Tots dos calcular el factorial de n. La versió de l'esquerra utilitza la recursivitat per fer-ho. La versió a la dreta utilitza iteració per fer-ho. 

I fixin-se, hem de declarar una variable d'un producte sencer. I després ens bucle. Sempre i quan n és més gran que 0, es continuar multiplicant aquest producte per n i decrementar n fins calculem el producte. Així doncs, aquestes dues funcions, una vegada més, fer exactament el mateix. Però ells no ho fan en exactament de la mateixa manera. 

Ara, és possible tenir més d'una base de cas o més d'una cas recursiu, depenent en el que la seva funció està tractant de fer. No està necessàriament només limitat a un sol cas base o un sol recursiva cas. Així que un exemple d'alguna cosa amb múltiples casos base podria ser la això- Sèrie de Fibonacci. 

Vostè pot recordar de dies d'escola primària que la seqüència de Fibonacci es defineix així- el primer element és 0. El segon element és 1. Tots dos són simplement per definició. 

Llavors es defineix tots els altres elements com la suma de n menys 1 i n almenys 2. Així que el tercer element seria 0 + 1 és 1. I llavors el quart element seria el segon element, 1, més el tercer element, 1. I això seria febrer. I així successivament i així successivament. 

Així que en aquest cas, tenim dos casos base. Si n és igual a 1, retorna 0. Si n és igual a 2, tornar 1. Altrament, torni Fibonacci de n almenys 1 més de Fibonacci de n almenys 2. 

Així que això és diversos casos base. Què passa amb múltiples casos recurrents? Bé, hi ha alguna cosa crida l'conjectura de Collatz. Jo no vaig a dir, vostè sap el que és això, perquè en realitat és el nostre últim problema per a aquest vídeo en particular. I és el nostre exercici per treballar junts. 

Així que aquí està el que el Collatz conjectura és-- que s'aplica a cada nombre enter positiu. I especula que és sempre és possible tornar 1 si vostè segueix aquests passos. Si n és 1, per. Tenim de nou a 1 si n és 1. 

Altrament, aneu a través d'aquest procés de nou a n dividit per 2. I veure si pot tornar a 1. Altrament, si n és imparell, anar a través d' aquest procés nou en 3n més 1, o 3 vegades N més 1. Així que aquí tenim un cas base. Si n és igual a 1, parar. No estem fent res més recursivitat. 

Però tenim dos casos recursives. Si n és parell, ho fem d'un recursiu cas, trucant n dividit per 2. Si n és imparell, fem un diferent cas recursiu en 3 vegades N més 1. 

I el que l'objectiu d'aquest vídeo és prendre un segon, fer una pausa en el video, i tractar d'escriure aquest funció recursiva Collatz on es passa en un valor n, i calcula quants passos pren per arribar a 1 si s'inicia a partir de n i vostè segueix aquests passos fins a dalt. Si n és 1, es triga 0 passos. En cas contrari, es va a fer un pas més però molts passos que es necessita en cada n dividit per 2 si n és parell, o 3n més 1 si n és imparell. 

Ara, m'he posat a la pantalla aquí un parell de coses de prova per a vostè, un parell de proves de casos per a vostè, per veure el que aquests diversos números Collatz són, i també una il·lustració dels passos que necessiten ser passat pel que pot sort de veure aquest procés en acció. Així que si n és igual a 1, Collatz de n és 0. Vostè no té a veure qualsevol cosa per aconseguir de nou a 1. Vostè és ja allà. 

Si n és 2, es necessita un pas per arribar a 1. Es comença amb 2. Bé, 2 no és igual a 1. Així que serà un pas més però moltes mesures que adquireix n dividit per 2. 

2 dividit per 2 és 1. Així que pren un pas més però molts passos que triga 1. 1 presa zero passos. 

Per a 3, com es pot veure, no hi ha uns quants passos involucrats. Es passa de 3. I després vas a 10, 5, 16, 8, 4, 2, 1. Porta set passos per tornar a 1. I com es pot veure, hi ha una parell d'altres casos de prova aquí per posar a prova el seu programa. Així que de nou, fer una pausa en el vídeo. I jo aniré a saltar de nou ara el que el procés real és aquí, el que aquesta conjectura és. 

A veure si pots esbrinar com definir Collatz de n de manera que calcula quants els passos que es necessita per arribar a 1. Així que espero que, d'haver detingut el vídeo i no està a l'espera de mi per donar-li la resposta aquí. Però si vostè és, així, aquí està la resposta de totes maneres. 

Així que aquí hi ha una possible definició de la funció de Collatz. La nostra base cas-- si n és igual a 1, tornem 0. No es necessita cap passos per arribar de nou a 1. 

Altrament, tenim dos casos-- recursiva per als números parells i un altre per imparell. La forma en què la prova de nombres parells és comprovar si n mod 2 és igual a 0. Això és bàsicament, una vegada més, fer la pregunta, si vostè recorda ho és-- mod si dividir n per 2 hi ha cap resta? Això seria un nombre parell. 

I així, si n mod 2 és igual a 0 és aquesta prova és un nombre parell. Si és així, vull tornar 1, perquè aquest és, sens dubte donant un pas més Collatz de qualsevol que sigui el nombre és la meitat de mi. En cas contrari, vull tornar 1 més Collatz de 3 vegades n més 1. Aquesta va ser l'altra pas recursiu que ens podria prendre per calcular el Collatz-- el nombre de passos que es necessita per tornar a 1 donat un nombre. Així que espero que aquest exemple Li va donar una mica d'una mostra de procediments recursius. Amb sort, vostè pensa codi és un poc més bella si s'apliquen d'una manera elegant, recursiu. Però fins i tot si no, la recursivitat és una eina realment poderosa, però. I el que és definitivament una cosa per obtenir el seu cap al voltant, perquè vostè serà capaç de crear programes molt interessants utilitzant recursivitat que d'altra manera podria ser complex per escriure si vostè està utilitzant loops i iteració. Sóc Doug Lloyd. Això és CS50.