>> ZAMYLA: A fin de comprender recursão, ten que
primeiro entender recursión.
Tendo recursão en programa proxecto significa que ten auto-referencial
definicións.
Estruturas de datos recursivas, por exemplo, son estruturas de datos que
inclúense na súas definicións.
Pero hoxe, imos centrar en funcións recursivas.
>> Lembre que as funcións de entradas, argumentos, e voltar un valor como o seu
saída representada polos Neste diagrama aquí.
Nós imos pensar no cadro como o corpo de a función, que contén o conxunto de
instrucións que interpretan o de entrada e proporcionar unha saída.
Dando un ollo ao interior do corpo de a función podería revelar chamadas a
outras funcións tamén.
Aproveitar esta función simple, foo, que ten unha única secuencia como entrada e
copias cantas letras esa secuencia ten.
O strlen función, para a lonxitude da corda, chámase, cuxa saída está
necesaria para a chamada a printf.
>> Agora, o que fai que unha función recursiva especial é que se chama.
Podemos representar esta recursiva chamar con esta frecha laranxa
Looping de volta a si mesmo.
Pero a execución en si de novo só pode facer outra chamada recursiva, e
outra e outra.
Pero funcións recursivas non pode ser infinita.
Teñen de acabar de algunha maneira, ou o seu programa será executado para sempre.
>> Entón, necesitamos atopar unha forma de rompe fóra das chamadas recursivas.
Chamamos iso de caso base.
Cando a condición de caso base é cumprida, a función devolve sen facer
outra chamada recursiva.
Tomé esta función, oi, unha función void que leva un int n como entrada.
O caso base ven en primeiro lugar.
Se n é menor que cero, imprimir e bye Voltar todos os demais casos, o
función imprimirá ola e executar a chamada recursiva.
Outra chamada á función con ola un valor de entrada diminúa.
>> Agora, aínda que imprimir ola, o función non rematará ata que nós
voltar o seu tipo de retorno, neste caso, nulo.
Así, para cada n distinto do caso base, esta función pode voltar ola ola
de n menos 1.
Xa que esta función non é nada, porén, que non explicitamente tipo de retorno aquí.
Nós imos realizar a función.
Entón, chamando ola (3) imprimirá ola e realizar ola (2) que executa ola (1) un
que executa ola (0), onde o condición caso base sexa cumprido.
Entón, oi (0) imprime bye e retorna.
>> Aceptar.
Polo tanto, agora que entendemos os principios básicos de funcións recursivas, que precisan
polo menos unha de base, así como un chamada recursiva, imos pasar a unha
exemplo máis significativo.
Un que non só devolver anular non importa o que.
>> Imos dar un ollo ao factorial operación máis comunmente usado en
cálculos de probabilidade.
Factorial de n é o produto de todos os enteiro positivo inferior
e igual a n.
Entón cinco factorial é 5 veces 4 veces 3 veces, 2 veces 1 para obter 120.
Catro factorial é 4 veces 3 veces 2 veces 1 para dar 24.
E a mesma regra se aplica para calquera número enteiro positivo.
>> Entón, como podemos escribir unha recursiva función que calcula o factorial
dunha serie de?
Ben, imos ter para identificar a caso base e da chamada recursiva.
A chamada recursiva será o mesmo para todos os casos, excepto para a base
caso, o que significa que nós imos ter que atopar un estándar que vai dar o noso
resultado desexado.
>> Para este exemplo, vexa como factorial 5 consiste en multiplicar 4 por 3 por 2 por 1
E esa mesma multiplicación se atopa aquí, o
definición de 4 factorial.
Así, vemos que 5 factorial é só 5 veces 4 factorial.
Agora é que este estándar é aplicable a 4 factorial ben?
Si
Vemos que 4 factorial contén o multiplicación 3 veces, 2 veces 1, o
mesma definición como 3 factorial.
Entón, 4 factorial é igual a catro veces tres factorial, e así por diante e así por diante a nosa
estándar varas ata o 1 de factorial, que por definición, é igual a 1.
>> Non hai outro positivo enteiros esquerda.
Polo tanto, temos o estándar para nosa chamada recursiva.
n factorial é igual a n veces o factorial de n menos 1.
E o noso caso base?
Isto vai ser só a nosa definición dun factorial.
>> Entón agora podemos pasar á escritura código para a función.
Para o caso base, teremos a condición n é igual a igual a 1, onde
imos voltar 1.
Despois de pasar á chamada recursiva, imos voltar n veces o
factorial de n menos 1.
>> Agora imos probar este noso.
Intentaremos factorial 4.
Pola nosa función é igual a 4 veces factorial (3).
Factorial (3) é igual a 3 veces factoriais (2).
Factorial (2) é igual a 2 veces factorial (1), que devolve 1.
Factorial (2) agora regresa 2 veces 1, 2.
Factorial (3) agora pode volver 3 veces 2, 6.
E, finalmente, factorial (4) retorna 4 veces 6, 24.
>> Se está atopando algunha dificultade coa chamada recursiva, finxir que
a función xa funciona.
O que quero dicir con isto é que ten que confiar nos seus chamadas recursivas para volver
os valores correctos.
Por exemplo, se eu sei que factorial (5) é igual a 5 veces
factorial (4), eu vou confiar que factorial (4) me vai dar 24.
Pense nisso como unha variable, se vontade, como se xa definido
factorial (4).
Así, para calquera factorial (n), é o produto de n e
o factorial anterior.
E iso factorial anterior obtense chamando
factorial de n menos 1.
>> Agora, vexa se pode aplicar un recursiva funcionar só.
Prema o seu terminal, ou run.cs50.net, e escribir unha función suma
que leva un enteiro n e devolve o suma de todos os positivos consecutivo
enteiros de 1 a n.
Escribín as sumas dalgúns valores para axudar a nosa.
En primeiro lugar, descubrir a condición caso base.
Entón, mire para suma (5).
Pode expresalo en termos doutra suma?
Agora, que tal suma (4)?
Como pode expresar suma (4) en termos doutra suma?
>> Despois de suma (5) e suma (4) expresada en termos doutras cantidades, consulte
se pode identificar un estándar para a suma (n).
Se non, proba algúns outros números e expresar as súas sumas en
termos de números.
Ao identificar patróns para discreto números, está ben na súa forma de
a identificación do estándar para calquera n.
>> A recursão é unha ferramenta moi poderosa, entón é claro que non está limitado a
funcións matemáticas.
A recursión se pode usar de forma moi eficaz cando se trata de árbores, por exemplo.
Escribe o curta en árbores para un máis profunda revisión, pero por agora
lembrar que as árbores de busca binária, en en particular, son constituídos por nós, cada
cun valor e dous punteiros do nodo.
Normalmente, este é representado pola nodo pai ter unha liña que apunta
ao nodo fillo esquerdo e un ao nodo fillo dereito.
A estrutura dunha busca binaria árbore presta-se ben
para unha investigación recursiva.
A chamada recursiva ou pasa no esquerda ou o no dereito, pero máis
de que, a curto árbore.
>> Digamos que queira realizar unha operación en cada nó único nunha árbore binaria.
Como pode ir sobre iso?
Ben, vostede podería escribir un recursiva función que executa a operación
no nodo pai e fai unha recursiva chamar a mesma función,
pasando á esquerda e nós fillos dereita.
Por exemplo, esta función, foo, que modifica o valor dun determinado nó e
todos os seus fillos a 1.
O caso base dun nulo causas nodo a función de retorno, indicando
que non hai ningún nodo esquerda en que a sub-árbore.
>> Imos atravesalo-la.
O primeiro pai é 13.
Imos cambiar o valor a 1, e logo chamar a nosa función na esquerda ben
como o dereito.
A función, foo, chámase á esquerda sub-árbore en primeiro lugar, de xeito que o nodo esquerdo
será trasladado a 1 e foo vontade ser chamados fillos dese nó,
primeiro á esquerda e despois á dereita, e así por diante e así por diante.
E dicirlles que as sucursais non teñen calquera máis nenos para que o mesmo proceso
seguirá para os nenos certas ata nós de toda árbore son
trasladado a 1.
>> Como podes ver, non está limitado para só unha chamada recursiva.
Así como moitos como vai comezar o traballo feito.
E se tivese unha árbore onde cada nó tivo tres fillos,
Esquerda, medio e dereita?
Como editar foo?
Ben, simple.
Tan só engadir outra chamada recursiva e pasar o punteiro do nodo central.
>> A recursão é moi poderoso e non mencionar elegante, pero pode ser un
concepto difícil ao principio, polo que non paciente e tomar o seu tempo.
Comeza o caso base.
Xeralmente é o máis fácil de identificar, e logo, pode traballar
atrás a partir de aí.
Vostede sabe que precisa para chegar ao seu caso base, de xeito que o poder
darlle algunhas suxestións.
Probe expresar un caso concreto en termos de outros casos, ou en sub-conxuntos.
>> Grazas por asistir a este curta.
Polo menos, agora pode comprender bromas como esta.
O meu nome é Zamyla, e este é CS50.
>> Tomé esta función, oi, un función void que leva
un int, n, como entrada.
O caso base ven en primeiro lugar.
Se n é menor que 0, impresión "Bye" e retorno.