[Música tocando] 

Doug LLOYD: Probablemente pensa que código só é usado para realizar unha tarefa. Escribe o para fora. Fai algo. Iso é moi fermoso isto. 

Vostede compilalo. Executar o programa. Está preparado para ir. 

Pero, cren ou non, se vostede codificar para un longo período de tempo, realmente pode chegar a ver código como algo que é bonito. Resolve un problema en un xeito moi interesante, ou hai algo realmente puro sobre a forma que parece. Podes estar rindo para min, pero é verdade. E recursão é un xeito a sorte de obter esa idea da fermosa código, de aspecto elegante. El resolve os problemas de forma que son interesantes, fácil de ver, e sorprendentemente curta. 

As obras xeito de recursão é, unha función recursiva defínese como unha función que chama Se como parte da súa execución. Isto pode parecer un pouco raro, e veremos un pouco sobre como funciona en un momento. Pero, de novo, estes procedementos recursiva son vai ser tan elegante porque eles van para solucionar este problema, sen Tendo en todas estas outras funcións ou estes longos loops. Vai ver que estes recursiva procedementos van ollar tan curto. E realmente van facer seu código ollar moito máis bonito. 

Vou che dar un exemplo deste para ver como un procedemento recursiva pode ser definido. Entón, se está familiarizado con este de clase de matemáticas hai moitos anos, Hai algo chamado función factorial, que adoita denotado como un signo de admiración, que defínese ao longo do todos os enteiros positivos. E a forma que n factorial calcúlase é vostede multiplicar todos os números de menos de ou igual a n together-- Todos os números enteiros inferiores a ou igual a n xuntos. 

Entón factorial 5 é 5 veces 4 veces 3 veces 2 veces 1. E 4 factorial é 4 veces 3 veces 2 veces 1 e así por diante. Comeza a idea. 

Como programadores, non usar n, signo de admiración. Entón, imos definir o factorial función como feito de n. E nós imos usar para crear factorial unha solución para un problema recursiva. E eu creo que pode atopar que é moito máis visual atractivo que o iterativo versión deste, que nós tamén imos dar un ollo en un momento. 

Entón, aquí están un par de xogo de palabras facts-- intended-- sobre o factorial-- función factorial. O factorial dun, como dixen, é unha. O factorial de 2 é 2 veces 1. O factorial de 3 a 3 veces 2 veces 1, e así por diante. Nós falamos sobre 4 e 5 xa. 

Pero mirando para iso, non é verdade? Non é só factorial 2 2 veces o factorial dun? Quero dicir, o factorial dun é un. Entón, por que non podemos simplemente dicir que, desde factorial 2 é 2 veces 1, É realmente só 2 veces o factorial dun? 

E entón estender esa idea, non é o factorial de 3 só a 3 veces o factorial de 2? E o factorial de 4 é 4 veces o factorial de 3, e así por diante? En realidade, o factorial de calquera número pode só ser expresado si tipo de realizalo la para sempre. Podemos tipo de xeneralizar o problema factorial Como é n veces os factorial de n menos 1. É n veces o produto todos os números menos ca min. 

Esta idea, esta xeneralización do problema, permítenos de forma recursiva definir a función factorial. Cando define unha función de forma recursiva, non hai dúas cousas que teñen que ser unha parte dela. Ten que ter unha cousa chamada caso base, o que, cando active-lo, deter o proceso recursivo. 

Se non, unha función que chama itself-- como pode imagine-- podería ir para sempre. Función chama a función chama chamadas de función a función chama a función. Se non ten unha forma para-lo, o seu programa será efectivamente detido en un loop infinito. Ha fallar eventualmente porque só pode ir sen memoria. Pero iso non vén ao caso. 

Necesitamos a ter algunha outra forma de deixar cousas alén do noso programa que deixa de funcionar, porque un programa que falla é probablemente non bonito ou elegante. E así chamamos este escenario de base. Esta é unha solución sinxela para un problema que para o proceso recursivo ocorra. Entón esta é unha parte da unha función recursiva. 

A segunda parte é o caso recursiva. E é aquí onde a recursão vai realmente ocorrer. Este é o lugar onde a función pode chamar a si mesma. 

Non vai chamar-se exactamente do mesmo xeito que foi chamado. Vai ser unha pequena variación que fai que o problema é intentando resolver un pouquiño máis pequeno. Pero xeralmente pasa o fanfarrão de resolver a maior parte da solución de para unha chamada diferente para abaixo da liña. 

Cal destes looks como é o caso base aquí? Cal destes miradas como o máis simple solución para un problema? Temos unha morea de factoriais, e poderiamos seguir indo on-- 6, 7, 8, 9, 10, e así por diante. 

Pero un deses miradas como un bo caso para ser o caso base. É unha solución moi sinxela. Non temos que facer nada especial. 

O factorial dun é un esbozo. Non temos que facer calquera multiplicación de todo. Parece que se imos para tratar de solucionar este problema, e necesitamos a deter o recursão nalgún lugar, nós probablemente quere deixar cando chegamos a 1. Non queremos deixar antes diso. 

Entón, se estamos definindo nosa función factorial, aquí está un esqueleto para como podemos facelo. Necesitamos conectar estes dous coisas- o caso base eo caso recursiva. ¿Que é o caso base? Se n é igual a 1, de regreso que é 1-- un problema moi sinxelo de resolver. 

O factorial dun é un. Non son 1 veces nada. É só un. É un feito moi fácil. E así que pode ser o noso caso base. Se conseguir pasar 1 a este función, imos voltar 1. 

Cal é a recursiva caso probablemente se parece? Para cada outro número ademais de un, que é o patrón? Ben, se estamos tomando o factorial de n, É n veces o factorial de n menos 1. 

Se estamos levando o factorial de 3, é 3 veces o factorial de 3 menos 1, ou 2. E por iso, se non estamos mirando para un, se non, retorno n veces os factorial de n menos 1. É moi sinxelo. 

E por unha cuestión de ter un pouco máis limpo e máis elegante código, sabemos que si ten lazos de liña única ou single liña desvíos condicionais, podemos librar de todos os claves en torno a eles. Así, podemos consolidar esa a iso. Isto exactamente a mesma como esta función. 

Eu só estou tirando o rizado cintas, porque hai só unha liña dentro destes desvíos condicionais. Así, estes se comportan de forma idéntica. Se n é igual a 1, de regreso 1. Se non, voltar n veces o factorial de n menos 1. Entón, nós estamos facendo o problema menor. Se n comeza como 5, imos volver 5 veces o factorial de catro. E veremos nun minuto cando falamos sobre a stack-- chamada noutro vídeo onde falamos sobre o chamar stack-- imos aprender sobre por que exactamente ese proceso funciona. 

Pero mentres factorial de 5 di volver 5 veces factorial de 4, e 4 vai dicir, OK, así, retorno 4 veces o factorial de 3. E como se pode ver, estamos tipo de aproximación 1. Estamos chegando máis preto e máis preto dese caso base. 

E xa que se loita o caso base, todas as funcións anteriores teño a resposta que estaban a buscar. Factorial de 2 estaba dicindo retorno 2 veces o factorial dun. Ben, factorial de 1 retorna 1. Así, o anuncio de convocatoria de factorial 2 pode volver 2 veces 1, e dar iso ao factorial 3, que está esperando por ese resultado. 

E, a continuación, pode calcular O seu resultado, 3 veces 2 é 6, e devolve-lo ó factorial de 4. E, de novo, temos un vídeo na pila de chamadas onde iso é ilustrado algo máis que o que estou dicindo agora. Pero é iso. Isto por si só, é a solución de calcular o factorial dun número. 

É só catro liñas de código. Iso é moi legal, non? É unha especie de sexy. 

Así, en xeral, pero non sempre, unha función recursiva poden substituír un circuíto nunha función non recursiva. Entón, aquí, de xeito conxunto, é o iterativo versión da función factorial. Ambos calcule exactamente o mesmo. 

Ambos calcular o factorial de n. A versión da esquerda usa recursão para facelo. A versión á dereita usa iteración para facelo. 

E observen, temos que declarar unha variable dun produto enteiro. E entón nós loop. Así, sempre que n é maior que 0, nós manter multiplicando este producto por n e diminuíndo n ata calculamos o produto. Así, estas dúas funcións, de novo, facer exactamente o mesmo. Pero eles non facelo en exactamente igual. 

Agora, é posible ter máis dunha base caso de un ou máis caso recursiva, dependendo en que a función está intentando facer. Non é necesariamente só limitado a un caso base ou a unha única recursiva caso. Entón, un exemplo de algo con varios casos base pode ser o o-- Secuencia de números de Fibonacci. 

Ten que se lembrar de días de escola primaria que a secuencia de Fibonacci defínese isto-- como o primeiro elemento é 0. O segundo elemento é 1. Ambos estes son só por definición. 

A continuación, as demais elementos defínese como a suma de n menos 1 e n menos 2. Así, o terceiro elemento 0 sería máis 1 é 1. E, a continuación, o cuarto elemento sería o segundo elemento, 1, máis o terceiro elemento, 1. E iso sería 2. E así por diante e así por diante. 

Polo tanto, neste caso, temos dous casos base. Se n é igual a 1, 0 regreso. Se n é igual a 2, o retorno 1. Se non, o regreso de Fibonacci n menos 1 máis Fibonacci n menos 2. 

Entón é iso varios casos base. E sobre varios casos recursiva? Así, hai algo chamado a conxectura de Collatz. Non vou dicir, vostede sabe o que é, porque é realmente o noso último problema para este vídeo particular. E é o noso exercicio para traballar en conxunto. 

Entón aquí está o que o Collatz conxectura é-- que se aplica a cada enteiro positivo. E especula que é sempre pode volver 1 se seguir estes pasos. Se n é 1, parar. Temos ao 1 se n é 1. 

Se non, pasar por iso proceso de novo en N dividida por 2. E vexa se pode obter de volta a 1. Se non, se n é impar, pasar por este proceso unha vez en 3N + 1, ou 3 veces n máis 1. Entón aquí temos un único caso base. Se n é igual a 1, pare. Non estamos facendo máis recursão. 

Pero temos dous casos recursiva. Se n é par, nós facemos unha recursiva caso, chamando n dividido por dous. Se n é impar, facemos unha diferente caso recursiva en 3 veces n máis 1. 

E así, o obxectivo para este vídeo é para tomar unha segunda, deter o vídeo, e tentar escribir este función recursiva Collatz onde pasar un valor n, e el calcula cantos pasos leva para chegar a 1 se comezar a partir de n e seguir os pasos anteriores. Se n é 1, que leva 0 etapas. Se non, vai dar un paso máis con todo moitos pasos que ten en ambos os n dividido por 2, se n é par, ou 3N +1 se n é impar. 

Agora, eu coloque na pantalla aquí un par de cousas proba para ti, un par de probas de casos para ti, a ver o que estes varios números de Collatz son, e tamén unha ilustración de que os pasos teñen que ser atravesado para que poida tipo de ver este proceso en acción. Así, se n é igual a 1, Collatz de n é 0. Non ten que facer algo para volver a 1. Xa está aí. 

Se n é 2, que leva un paso para chegar a 1. Comeza con dous. Ben, 2 non é igual a 1. Por iso, será un paso con todo, máis moitos pasos de TI n asume dividida por 2. 

2 divídese por 2 1. Por iso, dá un paso máis con todo moitos pasos que leva a 1. 1 comporta de cero pasos. 

Para 3, como se pode ver, hai moi poucos pasos implicados. Vai de 3. E entón vai para 10, 5, 16, 8, 4, 2, 1. Leva sete pasos para volver a un. E como se pode ver, hai unha algúns outros casos de proba aquí para probar o seu programa. Entón, de novo, deter o vídeo. E eu vou ir para atrás agora o que o proceso real é aquí, o que é esa conxectura. 

Vexa se pode descubrir como configurar Collatz n de xeito que calcula cantos os pasos que leva para chegar a 1. Polo tanto, esperamos que, fixo unha pausa o vídeo e non están só esperando por min para darlle a resposta aquí. Pero se é así, aquí está a resposta de todos os xeitos. 

Entón aquí está unha posible definición da función Collatz. Nosa base case-- se n é igual a 1, volvemos 0. Non hai que calquera pasos para obter de volta a un. 

Se non, temos dous cases-- recursiva unha para números pares e outro para impar. O xeito que eu probar a números pares é verificar que n mod 2 é igual a 0. Isto é, basicamente, unha vez máis, facer a pregunta, se recorda o que é-- mod si divide n por 2 que non hai resto? Iso sería un número par. 

E por iso, se n mod 2 é igual a 0 é proba é este un número par. Se é así, eu quero volver 1, porque este é sempre dando un paso máis aló de Collatz o que número é metade de min. Se non, eu quero volver 1 ademais de Collatz de 3 veces n máis 1. Esa foi a outra mentres que recursiva podería tomar para calcular o Collatz-- o número de pasos fai falta para volver 1 dado un número. Polo tanto, esperamos que este exemplo deulle un pouco dun gusto de procedementos recursiva. Con sorte, pensas que é un código pouco máis bonito se aplicado dunha forma elegante, recursiva. Pero aínda que non, a recursividade é unha realmente poderosa ferramenta, con todo. E por iso é sempre algo para obter a súa cabeza en torno, porque vai ser capaz de crear programas moi legal usando recursão que doutro xeito poderían ser complexo para escribir se está a usar loops e iteración. Eu son Doug Lloyd. Este é CS50.