[Música tocando] 

DOUG LLOYD: Você provavelmente pensa que código é apenas usado para realizar uma tarefa. Você escreve-o para fora. Ele faz alguma coisa. Isso é muito bonito isso. 

Você compilá-lo. Você executar o programa. Você está pronto para ir. 

Mas, acredite ou não, se você codificar para um longo período de tempo, você realmente pode vir para ver código como algo que é bonito. Resolve um problema em uma maneira muito interessante, ou há algo realmente puro sobre a maneira que parece. Você pode estar rindo para mim, mas é verdade. E recursão é uma maneira a sorte de obter essa idéia da bela código, de aparência elegante. Ele resolve os problemas de uma forma que são interessantes, fácil de visualizar, e surpreendentemente curta. 

As obras maneira de recursão é, uma função recursiva é definida como uma função que chama -se como parte de sua execução. Isso pode parecer um pouco estranho, e vamos ver um pouco sobre como isso funciona em um momento. Mas, novamente, estes procedimentos recursiva são vai ser tão elegante porque eles vão para resolver este problema, sem Tendo em todas estas outras funções ou estes longos loops. Você vai ver que estes recursiva procedimentos estão indo olhar tão curto. E eles realmente vão fazer seu código olhar muito mais bonito. 

Vou te dar um exemplo deste para ver como um procedimento recursiva pode ser definido. Então, se você estiver familiarizado com este de aula de matemática há muitos anos, Há algo chamado de função fatorial, que é normalmente denotado como um ponto de exclamação, que é definida ao longo do todos os inteiros positivos. E a maneira que n factorial é calculado é você multiplicar todos os números de menos de ou igual a n together-- Todos os números inteiros inferiores a ou igual a n juntos. 

Então fatorial 5 é 5 vezes 4 vezes 3 vezes 2 vezes 1. E 4 fatorial é 4 vezes 3 vezes 2 vezes 1 e assim por diante. Você começa a idéia. 

Como programadores, nós não usar n, ponto de exclamação. Então, vamos definir o fatorial função como fato de n. E nós vamos usar para criar fatorial uma solução para um problema recursiva. E eu acho que você pode encontrar que é muito mais visualmente atraente do que o iterativo versão deste, que nós também vamos dar uma olhada em um momento. 

Então, aqui estão um par de trocadilho facts-- intended-- sobre o factorial-- função fatorial. O fatorial de um, como eu disse, é uma. O fatorial de 2 é 2 vezes 1. O fatorial de 3 a 3 vezes 2 vezes 1, e assim por diante. Nós conversamos sobre 4 e 5 já. 

Mas olhando para isso, não é verdade? Não é apenas fatorial 2 2 vezes o fatorial de um? Quero dizer, o fatorial de um é um. Então, por que não podemos simplesmente dizer que, desde fatorial 2 é 2 vezes 1, É realmente apenas 2 vezes o fatorial de um? 

E então estender essa idéia, não é o fatorial de 3 apenas a 3 vezes o fatorial de 2? E o fatorial de 4 é 4 vezes o fatorial de 3, e assim por diante? Na verdade, o fatorial de qualquer número pode apenas ser expresso se nós tipo de realizá-la para sempre. Podemos tipo de generalizar o problema fatorial Como é n vezes os fatorial de n menos 1. É n vezes o produto de todos os números menos do que eu. 

Esta idéia, esta generalização do problema, permite-nos de forma recursiva definir a função fatorial. Quando você define uma função de forma recursiva, não há duas coisas que precisam ser uma parte dela. Você precisa ter uma coisa chamada caso base, o que, quando você acioná-lo, irá parar o processo recursivo. 

Caso contrário, uma função que chama itself-- como você pode imagine-- poderia ir para sempre. Função chama a função chama as chamadas de função a função chama a função. Se você não tem uma maneira pará-lo, o seu programa vai ser efetivamente preso em um loop infinito. Ele irá falhar, eventualmente, porque ele vai ficar sem memória. Mas isso não vem ao caso. 

Nós precisamos de ter alguma outra maneira de parar coisas além do nosso programa que deixa de funcionar, porque um programa que falha é provavelmente não bonito ou elegante. E assim nós chamamos este cenário de base. Esta é uma solução simples para um problema que pára o processo recursivo ocorra. Então essa é uma parte da uma função recursiva. 

A segunda parte é o caso recursiva. E é aqui que a recursão vai realmente acontecer. Este é o lugar onde o função irá chamar a si mesma. 

Não vai chamar-se exatamente da mesma forma que foi chamado. Vai ser uma pequena variação que faz com que o problema é tentando resolver um pouquinho menor. Mas geralmente passa o fanfarrão de resolver a maior parte da solução de para uma chamada diferente para baixo da linha. 

Qual desses looks como é o caso base aqui? Qual desses olhares como o mais simples solução para um problema? Temos um monte de fatoriais, e poderíamos continuar indo on-- 6, 7, 8, 9, 10, e assim por diante. 

Mas um desses olhares como um bom caso para ser o caso base. É uma solução muito simples. Nós não temos que fazer nada especial. 

O fatorial de um é apenas um. Nós não temos que fazer qualquer multiplicação de todo. Parece que se vamos para tentar resolver este problema, e nós precisamos de parar o recursão em algum lugar, nós provavelmente quer parar quando chegarmos a 1. Nós não queremos parar antes disso. 

Então, se estamos definindo nossa função fatorial, aqui está um esqueleto para como podemos fazer isso. Precisamos de ligar esses dois coisas- o caso base eo caso recursiva. O que é o caso base? Se n é igual a 1, de regresso que é 1-- um problema muito simples de resolver. 

O fatorial de um é um. Não são 1 vezes nada. É apenas um. É um fato muito fácil. E assim que pode ser o nosso caso base. Se conseguir passar 1 a este função, vamos retornar 1. 

Qual é a recursiva caso provavelmente se parece? Para cada outro número além de um, que é o padrão? Bem, se nós estamos tomando o fatorial de n, É n vezes o fatorial de n menos 1. 

Se nós estamos levando o fatorial de 3, é 3 vezes o fatorial de 3 menos 1, ou 2. E por isso, se nós não estamos olhando para um, caso contrário, retorno n vezes os fatorial de n menos 1. É bastante simples. 

E por uma questão de ter um pouco mais limpo e mais elegante código, sabemos que se nós tem laços de linha única ou single-line desvios condicionais, podemos nos livrar de todos os chaves em torno deles. Assim, podemos consolidar essa a isso. Isto tem exactamente a mesma como esta funcionalidade. 

Eu só estou tirando o encaracolado cintas, porque há apenas uma linha dentro desses desvios condicionais. Assim, estes se comportam de forma idêntica. Se n é igual a 1, de regresso 1. Caso contrário, retornar n vezes o fatorial de n menos 1. Então, nós estamos fazendo o problema menor. Se n começa como 5, vamos voltar 5 vezes o fatorial de quatro. E vamos ver em um minuto quando falamos sobre a stack-- chamada em outro vídeo onde falamos sobre o chamar stack-- vamos aprender sobre por que exatamente esse processo funciona. 

Mas enquanto fatorial de 5 diz voltar 5 vezes fatorial de 4, e 4 vai dizer, OK, bem, retorno 4 vezes o fatorial de 3. E como você pode ver, estamos tipo de aproximação 1. Estamos chegando mais perto e mais perto desse caso base. 

E uma vez que nós batemos o caso base, todas as funções anteriores tenho a resposta que eles estavam procurando. Fatorial de 2 estava dizendo retorno 2 vezes o fatorial de um. Bem, fatorial de 1 retorna 1. Assim, o convite à apresentação de fatorial de 2 pode voltar 2 vezes 1, e dar isso de volta para fatorial 3, que está esperando por esse resultado. 

E, em seguida, ele pode calcular Seu resultado, 3 vezes 2 é 6, e devolvê-lo ao fatorial de 4. E, novamente, temos um vídeo na pilha de chamadas onde isso é ilustrado um pouco mais do que o que estou dizendo agora. Mas é isso. Isto por si só, é a solução de calcular o fatorial de um número. 

É apenas quatro linhas de código. Isso é muito legal, né? É uma espécie de sexy. 

Assim, em geral, mas não sempre, uma função recursiva podem substituir um circuito numa função não recursiva. Então, aqui, lado a lado, é o iterativo versão da função fatorial. Ambos calcule exatamente a mesma coisa. 

Ambos calcular o fatorial de n. A versão do lado esquerdo usa recursão para fazê-lo. A versão à direita usa iteração para fazê-lo. 

E observem, nós temos que declarar uma variável de um produto inteiro. E então nós loop. Assim, desde que n é maior do que 0, nós manter multiplicando esse produto por n e diminuindo n até calculamos o produto. Assim, estas duas funções, de novo, fazer exatamente a mesma coisa. Mas eles não fazê-lo em exactamente da mesma forma. 

Agora, é possível ter mais do que uma base caso de um ou mais caso recursiva, dependendo em que a função está tentando fazer. Você não é necessariamente apenas limitado a um caso base ou a uma única recursiva caso. Então, um exemplo de algo com vários casos base pode ser o o-- Seqüência de números de Fibonacci. 

Você deve se lembrar de dias de escola primária que a seqüência de Fibonacci é definido isto-- como o primeiro elemento é 0. O segundo elemento é 1. Ambos esses são apenas por definição. 

Em seguida, todos os outros elementos é definida como a soma de n menos 1 e n menos 2. Assim, o terceiro elemento 0 seria mais 1 é 1. E, em seguida, o quarto elemento seria o segundo elemento, 1, mais o terceiro elemento, 1. E isso seria 2. E assim por diante e assim por diante. 

Portanto, neste caso, temos dois casos base. Se n é igual a 1, 0 regresso. Se n é igual a 2, o retorno 1. Caso contrário, o retorno de Fibonacci de n menos 1 mais Fibonacci de n menos 2. 

Então é isso vários casos base. E sobre vários casos recursiva? Bem, há algo chamado a conjectura de Collatz. Eu não vou dizer, você sabe o que é, porque é realmente o nosso último problema para este vídeo particular. E é o nosso exercício para trabalhar em conjunto. 

Então aqui está o que o Collatz conjectura é-- que se aplica a cada inteiro positivo. E ele especula que ele é sempre possível voltar 1 se você seguir estes passos. Se n é 1, parar. Temos de volta para 1 se n for 1. 

Caso contrário, passar por isso processo novamente em N dividida por 2. E veja se você pode obter de volta para 1. Caso contrário, se n for ímpar, passar por este processo mais uma vez em 3n + 1, ou 3 vezes n mais 1. Então aqui nós temos um único caso base. Se n é igual a 1, pare. Nós não estamos fazendo mais recursão. 

Mas temos dois casos recursiva. Se n é par, nós fazemos uma recursiva caso, chamando n dividido por dois. Se n é ímpar, fazemos uma diferente caso recursiva em 3 vezes n mais 1. 

E assim, a meta para este vídeo é para tomar uma segunda, pausar o vídeo, e tentar escrever este função recursiva Collatz onde você passar um valor n, e ele calcula quantos passos leva para chegar a 1 se você começar a partir de n e você seguir os passos acima. Se n é 1, que leva 0 etapas. Caso contrário, ele vai dar um passo além no entanto muitos passos que leva em ambos os n dividido por 2, se n for par, ou 3n + 1 se n é ímpar. 

Agora, eu coloquei na tela aqui um par de coisas teste para você, um par de testes de casos para você, para ver o que esses vários números de Collatz são, e também uma ilustração de que as etapas precisam ser atravessado para que você possa tipo de ver este processo em ação. Assim, se n for igual a 1, Collatz de n é 0. Você não tem que fazer qualquer coisa para voltar para 1. Você já está lá. 

Se n for 2, que leva um passo para chegar a 1. Você começa com dois. Bem, 2 não é igual a 1. Por isso, vai ser um passo no entanto, mais muitos passos de TI n assume dividida por 2. 

2 é dividido por 2 1. Por isso, dá um passo além no entanto muitos passos que leva para 1. 1 comporta de zero passos. 

Para 3, como você pode ver, há muito poucos passos envolvidos. Você vai de 3. E então você vai para 10, 5, 16, 8, 4, 2, 1. Leva sete passos para voltar a um. E como você pode ver, há uma alguns outros casos de teste aqui para testar seu programa. Então, novamente, pausar o vídeo. E eu vou saltar para trás agora o que o processo real é aqui, o que é essa conjectura. 

Veja se você pode descobrir como definir Collatz de n de modo que ele calcula quantos os passos que leva para chegar a 1. Portanto, esperamos que, você fez uma pausa o vídeo e você não está apenas esperando por mim para dar-lhe a resposta aqui. Mas se você é, bem, aqui está a resposta de qualquer maneira. 

Então aqui está uma possível definição da função Collatz. Nossa base case-- se n for igual a 1, voltamos 0. Não é preciso qualquer passos para obter de volta a um. 

Caso contrário, temos dois cases-- recursiva uma para números pares e outra para ímpar. A maneira que eu testar para números pares é verificar se n mod 2 é igual a 0. Isto é, basicamente, mais uma vez, fazer a pergunta, se você se lembra o que é-- mod se eu divide n por 2 que não há restante? Isso seria um número par. 

E por isso, se n mod 2 é igual a 0 é teste é este um número par. Se assim for, eu quero voltar 1, porque este é definitivamente dando um passo além de Collatz o que número é metade de mim. Caso contrário, eu quero voltar 1 além de Collatz de 3 vezes n mais 1. Essa foi a outra passo que recursiva poderia tomar para calcular o Collatz-- o número de passos é preciso para voltar 1 dado um número. Portanto, esperamos que, este exemplo deu-lhe um pouco de um gosto de procedimentos recursiva. Com sorte, você acha que é um código pouco mais bonito se implementado de uma forma elegante, recursiva. Mas mesmo se não, a recursividade é uma realmente poderosa ferramenta, no entanto. E por isso é definitivamente algo para obter a sua cabeça em torno, porque você vai ser capaz de criar programas muito legal usando recursão que de outro modo poderiam ser complexo para escrever se você estiver usando loops e iteração. Eu sou Doug Lloyd. Este é CS50.