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.