ZAMYLA: A fim de compreender recursão, você deve primeiro entender recursão. Tendo recursão em programa projeto significa que você tem auto-referencial definições. Estruturas de dados recursivas, por exemplo, são estruturas de dados que incluem-se na suas definições. Mas hoje, vamos focar em funções recursiva. 

Lembre-se que as funções de ter entradas, argumentos, e retornar um valor como o seu saída representada pelos Neste diagrama aqui. Nós vamos pensar na caixa como o corpo de a função, contendo o conjunto de instruções que interpretam o de entrada e fornecer uma saída. Dando uma olhada no interior do corpo de a função poderia revelar chamadas para outras funções também. Aproveite esta função simples, foo, que tem uma única seqüência como entrada e cópias quantas letras essa seqüência tem. O strlen função, para o comprimento da corda, é chamado, cuja saída está necessária para a chamada para printf. 

Agora, o que faz com que uma função recursiva especial é que ele se chama. Podemos representar esta recursiva chamar com esta seta laranja looping de volta para si mesmo. Mas a execução em si novamente só irá fazer outra chamada recursiva, e outra e outra. Mas funções recursivas não pode ser infinita. Eles têm de acabar de alguma forma, ou o seu programa será executado para sempre. 

Então, precisamos encontrar uma maneira de quebrar fora das chamadas recursivas. Chamamos isso de caso base. Quando a condição de caso base é cumprida, a função retorna sem fazer outra chamada recursiva. Tome esta função, oi, uma função void que leva um int n como entrada. O caso base vem em primeiro lugar. Se n é menor que zero, imprimir e bye voltar Para todos os outros casos, o função irá imprimir oi e executar a chamada recursiva. Outra chamada para a função com oi um valor de entrada diminua. 

Agora, mesmo que imprimir oi, o função não terminará até que nós retornar seu tipo de retorno, neste caso, nulo. Assim, para cada n diferente do caso base, esta função irá retornar oi oi de n menos 1. Uma vez que esta função não é nada, porém, que não explicitamente tipo de retorno aqui. Nós vamos executar a função. Então, chamando oi (3) irá imprimir oi e executar oi (2) que executa oi (1) um que executa oi (0), onde o condição caso base seja cumprido. Então, oi (0) imprime bye e retorna. 

OK. Portanto, agora que entendemos os princípios básicos de funções recursivas, que eles precisam pelo menos uma de base, assim como um chamada recursiva, vamos passar para uma exemplo mais significativo. Um que não apenas retornar anular não importa o que. 

Vamos dar uma olhada no fatorial operação mais comumente usado em cálculos de probabilidade. Factorial de n é o produto de todas as inteiro positivo inferior e igual a n. Então cinco fatorial é 5 vezes 4 vezes 3 vezes 2 vezes 1 para se obter 120. Quatro fatorial é 4 vezes 3 vezes 2 vezes 1 para dar 24. E a mesma regra se aplica para qualquer número inteiro positivo. 

Então, como podemos escrever uma recursiva função que calcula o fatorial de um número de? Bem, vamos precisar para identificar a caso base e da chamada recursiva. A chamada recursiva será o mesmo para todos os casos, exceto para a base caso, o que significa que nós vamos ter que encontrar um padrão que vai nos dar o nosso resultado desejado. 

Para este exemplo, veja como fatorial 5 consiste em multiplicar 4 por 3 por 2 por 1 E essa mesma multiplicação se encontra aqui, o definição de 4 fatorial. Assim, vemos que 5 fatorial é apenas 5 vezes 4 fatorial. Agora é que este padrão se aplica a 4 factorial bem? Sim. Vemos que 4 fatorial contém o multiplicação 3 vezes 2 vezes 1, o mesma definição como 3 fatorial. Então, 4 fatorial é igual a quatro vezes três fatorial, e assim por diante e assim por diante a nossa padrão varas até 1 de fatorial, que por definição, é igual a 1. 

Não há outro positivo inteiros esquerda. Portanto, temos o padrão para nossa chamada recursiva. n fatorial é igual a n vezes o fatorial de n menos 1. E o nosso caso base? Isso vai ser apenas a nossa definição de um fatorial. 

Então agora podemos passar para a escrita código para a função. Para o caso base, teremos a condição n é igual a igual a 1, onde vamos retornar 1. Depois de passar para a chamada recursiva, vamos voltar n vezes o fatorial de n menos 1. 

Agora vamos testar este nosso. Vamos tentar fatorial 4. Por nossa função é igual a 4 vezes fatorial (3). Factorial (3) é igual a 3 vezes fatoriais (2). Factorial (2) é igual a 2 vezes factorial (1), que retorna 1. Fatorial (2) agora retorna 2 vezes 1, 2. Fatorial (3) agora pode retornar 3 vezes 2, 6. E, finalmente, fatorial (4) retorna 4 vezes 6, 24. 

Se você está encontrando alguma dificuldade com a chamada recursiva, fingir que a função já funciona. O que quero dizer com isso é que você deve confiar em seus chamadas recursivas para voltar os valores corretos. Por exemplo, se eu sei que fatorial (5) é igual a 5 vezes fatorial (4), eu vou confiar que fatorial (4) vai me dar 24. Pense nisso como uma variável, se você vontade, como se você já definido fatorial (4). Assim, para qualquer fatorial (n), é o produto de n e o fatorial anterior. E isso fatorial anterior é obtida chamando fatorial de n menos 1. 

Agora, veja se você pode implementar um recursiva funcionar sozinho. Carregue o seu terminal, ou run.cs50.net, e escrever uma função soma que leva um inteiro n e retorna o soma de todos os positivo consecutivo inteiros de 1 a n. Eu escrevi as somas de alguns valores para ajudá-lo a nossa. Em primeiro lugar, descobrir a condição caso base. Então, olhe para soma (5). Você pode expressá-lo em termos de outra soma? Agora, que tal soma (4)? Como você pode expressar soma (4) em termos de outra soma? 

Depois de ter soma (5) e soma (4) expressa em termos de outras quantias, consulte se você pode identificar um padrão para a soma (n). Se não, tente alguns outros números e expressar suas somas em termos de outros números. Ao identificar padrões para discreto números, você está bem em sua maneira de a identificação do padrão para qualquer n. 

A recursão é uma ferramenta muito poderosa, então é claro que ele não está limitado a funções matemáticas. A recursão pode ser usado de forma muito eficaz quando se trata de árvores, por exemplo. Confira o curta em árvores para um mais profunda revisão, mas por agora lembrar que as árvores de busca binária, em em particular, são constituídos por nós, cada com um valor e dois ponteiros do nó. Normalmente, este é representado pela nó pai ter uma linha que aponta para o nó filho esquerdo e um para o nó filho direito. A estrutura de uma pesquisa binária árvore presta-se bem para uma pesquisa recursiva. A chamada recursiva ou passa no esquerda ou o nó direito, mas mais de que, a curto árvore. 

Digamos que você queira executar uma operação em cada nó único em uma árvore binária. Como você pode ir sobre isso? Bem, você poderia escrever um recursiva função que executa a operação no nó pai e faz uma recursiva ligar para a mesma função, passando a esquerda e nós filhos direita. Por exemplo, esta função, foo, que altera o valor de um determinado nó e todos os seus filhos a 1. O caso base de um nulo causas nó a função de retorno, indicando que não há nenhum nó esquerda em que a sub-árvore. 

Vamos atravessá-la. O primeiro pai é 13. Vamos mudar o valor para 1, e em seguida, chamar a nossa função na esquerda bem como o direito. A função, foo, é chamado à esquerda sub-árvore em primeiro lugar, de modo que o nó esquerdo será transferido para 1 e foo vontade ser chamados filhos desse nó, primeiro à esquerda e depois à direita, e assim por diante e assim por diante. E dizer-lhes que as sucursais não têm qualquer mais crianças para que o mesmo processo continuará para as crianças certas até nós de toda a árvore são transferido para 1. 

Como você pode ver, você não está limitado para apenas uma chamada recursiva. Assim como muitos como vai começar o trabalho feito. E se você tivesse uma árvore onde cada nó teve três filhos, Esquerda, meio e direita? Como você editar foo? Bem, simples. Basta adicionar outra chamada recursiva e passar o ponteiro do nó central. 

A recursão é muito poderoso e não mencionar elegante, mas pode ser um conceito difícil no início, por isso não paciente e tomar o seu tempo. Comece com o caso base. Geralmente é o mais fácil de identificar, e, em seguida, você pode trabalhar trás a partir daí. Você sabe que precisa para chegar ao seu caso base, de modo que o poder dar-lhe algumas sugestões. Tente expressar um caso específico em termos de outros casos, ou em sub-conjuntos. 

Obrigado por assistir a este curta. Pelo menos, agora você pode entender piadas como esta. Meu nome é Zamyla, e este é CS50. 

Tome esta função, oi, um função void que leva um int, n, como entrada. O caso base vem em primeiro lugar. Se n for menor do que 0, impressão "Bye" e retorno.