>> 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.