ZAMYLA: Con el fin de entender recursividad, se debe primero entender la recursividad. Tener la recursividad en el programa de diseño de medios que tiene autorreferencial definiciones. Estructuras de datos recursivas, por ejemplo, son estructuras de datos que incluir a sí mismos en sus definiciones. Pero hoy en día, nos vamos a centrar en funciones recursivas. 

Recordemos que las funciones necesitan insumos, argumentos y devuelve un valor como su de salida representado por este diagrama aquí. Ya pensaremos en la caja como el cuerpo de la función, que contiene el conjunto de instrucciones que interpretan el de entrada y proporcionar una salida. Tomando una mirada más cercana en el interior del cuerpo de la función podría revelar las llamadas a otras funciones también. Tome esta función simple, foo, que toma una sola cadena como entrada y impresiones de cuántas letras esa cadena tiene. El strlen función, por longitud de la cadena, se llama, cuya salida es requerido para la llamada a printf. 

Ahora, lo que hace una función recursiva especial es que se llama a sí misma. Podemos representar este recursiva llamar con esta flecha naranja bucle de nuevo a sí mismo. Pero la ejecución en sí de nuevo sólo se realizar otra llamada recursiva, y otro y otro. Pero las funciones recursivas no puede ser infinito. Tienen que acabar de alguna manera, o en su programa se ejecutará siempre. 

Así que tenemos que encontrar una manera de romper de las llamadas recursivas. A esto le llamamos el caso base. Cuando se cumple la condición de caso base, la función devuelve sin hacer otra llamada recursiva. Tome esta función, hi, una función void que toma un entero n como entrada. El caso base es lo primero. Si n es menor que cero, adiós de impresión y volver Para todos los demás casos, el función imprimirá hi y ejecutar la llamada recursiva. Otra llamada a la función con hi un valor de entrada decrementa. 

Ahora, a pesar de que imprimimos hi, la función no terminará hasta que devolver su tipo de retorno, en este caso sin efecto. Así, por cada n que no sea el caso base, esta función hi hi volverá de n menos 1. Dado que esta función no es válida, sin embargo, que no se escriba explícitamente regreso aquí. Acabábamos ejecutaremos la función. Así que llamar hi (3) imprimirá hola y ejecutar hi (2), que ejecuta hi (1) una que ejecuta hi (0), en el que el se cumple la condición de caso base. Así hi (0) imprime bye y vuelve. 

Aceptar. Así que ahora que entendemos los fundamentos de la funciones recursivas, que necesitan al menos un caso base, así como un llamada recursiva, vamos a pasar a un ejemplo más significativo. Uno que no sólo volver anular no importa qué. 

Vamos a echar un vistazo a el factorial operación más comúnmente utilizado en cálculos de probabilidad. Factorial de n es el producto de todos los número entero positivo menor e igual a n. Así que cinco factorial es 5 veces 4 veces 3 veces 2 veces 1 para dar 120. Cuatro factorial es 4 veces 3 veces 2 veces 1 para dar 24. Y se aplica la misma regla a cualquier número entero positivo. 

Entonces, ¿cómo podríamos escribir una recursiva función que calcula el factorial de un número? Bueno, vamos a necesitar para identificar tanto el caso base y la llamada recursiva. La llamada recursiva será el mismo para todos los casos excepto para la base caso, lo que significa que vamos a tener que encontrar un patrón que nos dará nuestra resultado deseado. 

Para este ejemplo, ver cómo 5 factorial implica multiplicar 4 por 3 por 2 por 1 Y esa misma multiplicación se encuentra aquí, el definición de 4 factorial. Así que vemos que 5 factorial es a sólo 5 veces 4 factorial. Ahora se aplica este patrón a 4 factorial, así? Sí. Vemos que 4 factorial contiene la multiplicar 3 veces 2 veces 1, el propia definición como 3 factorial. Así factorial 4 es igual a 4 veces 3 factorial, y así sucesivamente y así sucesivamente nuestra patrón de palos hasta 1 factorial, la cual por definición es igual a 1. 

No hay otra positiva enteros fueron. Así que tenemos el modelo para nuestra llamada recursiva. n factorial es igual a n veces el factorial de n menos 1. Y nuestro caso base? Eso acaba de ser nuestra definición de 1 factorial. 

Así que ahora podemos pasar a la escritura código de la función. Para el caso base, que tendremos la condición n es igual a es igual a 1, en los que le devolveremos 1. Luego de pasar a la llamada recursiva, volveremos n veces el factorial de n menos 1. 

Ahora vamos a probar esta nuestra. Probemos factorial 4. Por nuestra función es igual a 4 veces factorial (3). Factorial (3) es igual a 3 veces factoriales (2). Factorial (2) es igual a 2 veces factorial (1), que devuelve 1. Factorial (2) ahora devuelve 2 tiempos 1, 2. Factorial (3) ahora puede regresar 3 veces 2, 6. Y, por último, factorial (4) devuelve 4 tiempos 6, 24. 

Si usted está encontrando alguna dificultad con la llamada recursiva, pretender que la función ya funciona. Lo que quiero decir con esto es que usted debe confiar en sus llamadas recursivas para volver los valores correctos. Por ejemplo, si yo sé que factorial (5) es igual a 5 veces factorial (4), voy a confiar en que factorial (4) me va a dar 24. Piense en ello como una variable, si voluntad, como si ya ha definido factorial (4). Así que para cualquier factorial (N), que es el producto de n y el factorial anterior. Y esto factorial anterior se obtiene llamando al factorial de n menos 1. 

Ahora, a ver si se puede implementar un recursiva funcionar a ti mismo. Carga tu terminal, o run.cs50.net, y escribir una función sum que toma un entero n y devuelve el suma de todas positiva consecutiva números enteros de n es 1. He escrito un vistazo a las sumas de algunos valores que le ayudarán a nuestra. En primer lugar, averiguar el condiciones del caso base. Entonces, mira suma (5). ¿Se puede expresar en términos de otra suma? Ahora, ¿qué pasa con suma (4)? ¿Cómo se puede expresar suma (4) en términos de otra suma? 

Una vez que tenga suma (5) y suma (4) expresado en términos de otras cantidades, consulte si se puede identificar una patrón para la suma (n). Si no, pruebe algunos otros números y expresar sus sumas en términos de otros números. Mediante la identificación de los patrones de discreta números, usted está bien en su manera de identificar el patrón para cualquier n. 

La recursividad es una herramienta muy poderosa, así que por supuesto no se limita a funciones matemáticas. La recursividad puede ser utilizado de manera muy eficaz cuando se trata de árboles, por ejemplo. Echa un vistazo a la corta de los árboles durante un opinión más a fondo, pero por ahora recordar que los árboles de búsqueda binarios, en en particular, se componen de nodos, cada uno con un valor y dos punteros de nodo. Por lo general, esto está representado por el nodo padre tiene una apuntando línea al nodo hijo izquierdo y uno al nodo hijo derecho. La estructura de una búsqueda binaria árbol se presta bien a una búsqueda recursiva. La llamada recursiva sea pasa en el izquierda o derecha en el nodo, pero más de que en el corto árbol. 

Digamos que usted quiere realizar una operación en cada nodo individual en un árbol binario. ¿Cómo podría usted ir sobre eso? Bueno, se podría escribir un recursivo la función que realiza la operación en el nodo padre y hace una recursiva llamar a la misma función, que pasa en la izquierda y nodos secundarios adecuados. Por ejemplo, esta función, foo, que cambia el valor de un nodo dado y todos sus hijos a la 1. El caso base de un nodo causas nulos la función para volver, lo que indica que no hay nodos dejado en ese sub-árbol. 

Vamos a caminar a través de él. El primero de los padres es de 13. Cambiamos el valor a 1, y luego llamamos nuestra función en el lado izquierdo, así como el derecho. La función, foo, se llama a la izquierda sub-árbol en primer lugar, por lo que el nodo izquierdo será reasignado a 1 y Foo se pidió a los niños de ese nodo, primero la izquierda y luego la derecha, y así sucesivamente y así sucesivamente. Y les digo que las ramas no tienen tener más hijos por lo que el mismo proceso continuará por los hijos derecha hasta los nodos de la totalidad de los árboles son reasignado a 1. 

Como puede ver, usted no está limitado a sólo una llamada recursiva. Al igual que todos los que conseguirá el trabajo hecho. ¿Qué pasa si usted tenía un árbol donde cada nodo tuvo tres hijos, Izquierda, Centro y Derecha? ¿Cómo editar foo? Bueno, simple. Sólo tiene que añadir otra llamada recursiva y pase el puntero del nodo intermedio. 

La recursividad es muy potente y no menciona elegante, pero puede ser un difícil concepto al principio, así que paciente y tómese su tiempo. Comience con el caso base. Por lo general es la más fácil de identificar, y entonces usted puede trabajar hacia atrás desde allí. Usted sabe que necesita para llegar a su caso base, por lo que el poder darle algunos consejos. Trate de expresar un caso específico en términos de otras causas o en sub-conjuntos. 

Gracias por ver este corto. Por lo menos, ahora puede hacerlo entender chistes como éste. Mi nombre es Zamyla, y esto es CS50. 

Tome esta función, hi, un void función que toma un int, n, como entrada. El caso base es lo primero. Si n es menor que 0, imprimir "Bye" y el retorno.