[REPRODUCCIÓN DE MÚSICA] 

DOUG LLOYD: Usted probablemente piensa que código sólo se utiliza para realizar una tarea. Usted escribe a cabo. Hace algo. Eso es practicamente todo. 

Usted compilarlo. Ejecuta el programa. Usted está bueno para ir. 

Pero lo creas o no, si codificar por un largo tiempo, en realidad se puede llegar a ver código como algo que es hermoso. Soluciona un problema en una forma muy interesante, o hay algo de verdad aseada sobre la forma en que se ve. Usted podría estar riendo a mí, pero es la verdad. Y recursividad es una forma para conseguir una especie de esta idea de la hermosa, de aspecto elegante código. Soluciona problemas de manera que son interesantes, fácil de visualizar, y sorprendentemente corto. 

Las obras manera recursividad es, una función recursiva se define como una función que llama a sí misma como parte de su ejecución. Esto puede parecer un poco extraño, y vamos a ver un poco acerca de cómo funciona esto en un momento. Pero, de nuevo, estos procedimientos recursivos son va a ser tan elegante porque van para resolver este problema sin teniendo todas estas otras funciones o estos largos bucles. Vas a ver que éstos recursiva procedimientos van a parecer tan corto. Y realmente se va a hacer su código parecen mucho más hermosa. 

Te voy a dar un ejemplo de esto para ver cómo un procedimiento recursivo puede definirse. Así que si usted está familiarizado con este de la clase de matemáticas, hace muchos años, Hay algo llamado el función factorial, que es generalmente denotado como un signo de exclamación, que se define sobre todos los enteros positivos. Y la forma en que n factorial se calcula está usted multiplica todos los números de menos de o igual a n juntos-- todos los números enteros de menos de o igual a n juntos. 

Así 5 factorial es 5 veces 4 veces 3 veces 2 veces 1. Y 4 factorial es 4 veces 3 veces 2 veces 1 y así sucesivamente. Usted consigue la idea. 

Como programadores, no lo hacemos utilizar n, signo de exclamación. Así que vamos a definir el factorial función como un hecho de n. Y vamos a utilizar factorial para crear una solución recursiva a un problema. Y creo que podría encontrar que es mucho más visual apelando a la iterativa versión de este, el cual también vamos a echar un vistazo a en un momento. 

Así que aquí hay un par de juego de palabras facts-- intended-- sobre la factorial-- función factorial. El factorial de 1, como ya he dicho, es 1. El factorial de 2 es 2 veces 1. El factorial de 3 es 3 Tiempos 2 Tiempos 1, y así sucesivamente. Hablamos de 4 y 5 ya. 

Pero al mirar a esto, no es esto cierto? ¿No es el factorial de 2 solo 2 veces el factorial de 1? Quiero decir, el factorial de 1 es 1. ¿Por qué no podemos simplemente decir que, desde factorial de 2 es 2 veces 1, es realmente sólo 2 veces el factorial de 1? 

Y luego extender esa idea, no es el factorial de 3 sólo 3 veces el factorial de 2? Y el factorial de 4 es 4 veces el factorial de 3, y así sucesivamente? De hecho, el factorial de cualquier número puede simplemente ser expresada si especie de llevar esto a cabo siempre. Podemos tipo de generalizar el problema factorial ya que es n veces los factorial de n menos 1. Es n veces el producto de todos los números menores que yo. 

Esta idea, esto generalización del problema, nos permite de forma recursiva definir la función factorial. Cuando se define una función recursiva, hay dos cosas que deben ser parte de ella. Usted necesita tener algo llamado caso base, que, cuando usted los activa, se detendrá el proceso recursivo. 

De lo contrario, una función que llama itself-- como se podría imagine-- podría continuar para siempre. Función llama a la función llama a las llamadas de función la función llama a la función. Si usted no tiene una forma para detenerlo, su programa será atrapado con eficacia en un bucle infinito. Será estrellarse finalmente, porque va a quedarse sin memoria. Pero eso no viene al caso. 

Tenemos que tener alguna otra forma de detener cosas además de nuestro programa de estrellarse, porque un programa que se estrella es Probablemente no es bello o elegante. Y así lo llamamos el caso base. Esta es una solución simple a un problema que se detiene el proceso recursivo que se produzcan. Así que esa es una parte de una función recursiva. 

La segunda parte es el caso recursivo. Y aquí es donde la recursividad en realidad tener lugar. Aquí es donde el función se llame a sí mismo. 

No va a llamarse exactamente de la misma manera que se llamaba. Será una ligera variación que hace que el problema es tratando de resolver un poquitín más pequeño. Pero en general, pasa la pelota de resolver la mayor parte de la solución a una llamada diferente en la línea. 

¿Cuál de estos looks como el caso base en esta lista? ¿Cuál de estos looks como el solución más sencilla a un problema? Tenemos un montón de factoriales, y podríamos continuar ir en-- 6, 7, 8, 9, 10, y así sucesivamente. 

Pero uno de estos parece un buen caso es el caso base. Es una solución muy simple. No tenemos que hacer nada especial. 

El factorial de 1 es 1. No tenemos que hacer ningún multiplicación en absoluto. Parece como si vamos para tratar de resolver este problema, y tenemos que detener la recursividad en alguna parte, probablemente queremos parar cuando llegamos a 1. No queremos que se detenga antes de eso. 

Así que si estamos definiendo nuestra función factorial, aquí está un esqueleto para cómo podemos hacer eso. Tenemos que conectar esos dos cosas-- el caso base y el caso recursivo. ¿Cuál es el caso base? Si n es igual a 1, volver 1-- eso es un problema muy simple de resolver. 

El factorial de 1 es 1. No son 1 veces nada. Es sólo 1. Es un hecho muy fácil. Y para que pueda ser nuestro caso base. Si nos pasamos 1 en este función, sólo tendremos que regresemos 1. 

¿Cuál es la recursiva caso probablemente parece? Por cada otro número además de 1, ¿cuál es el patrón? Bueno, si estamos tomando el factorial de n, Es en momentos n el factorial de n menos 1. 

Si estamos tomando el factorial de 3, que es 3 veces el factorial de 3 menos 1, o 2. Y por lo que si no estamos mirando a 1, de lo contrario retorno n veces los factorial de n menos 1. Es bastante sencillo. 

Y por el bien de tener un poco más limpia y más elegante de código, saber que si tenemos bucles de una sola línea o de una sola línea de saltos condicionales, podemos deshacernos de toda la llaves alrededor de ellos. Así que podemos consolidar este a esto. Esto tiene exactamente el mismo funcionalidad que esto. 

Sólo estoy quitando el rizado apoyos, porque sólo hay una línea dentro de esas ramas condicionales. Así que estos se comportan de forma idéntica. Si n es igual a 1, volver 1. De lo contrario volverá n veces el factorial de n menos 1. Así que estamos haciendo el problema más pequeño. Si n comienza como 5, vamos a volver 5 veces el factorial de 4. Y veremos en un minuto cuando hablamos acerca de la stack-- llamada en otro video donde se habla de la llamar stack-- aprenderemos acerca de por qué exactamente este proceso funciona. 

Pero mientras factorial de 5 dice volver 5 veces factorial de 4, y 4 se va a decir, bien, bien, el regreso 4 veces el factorial de 3. Y como se puede ver, estamos tipo de acercarse a 1. Estamos cada vez más cerca y más cercana a la del caso base. 

Y una vez que llegamos a la hipótesis de base, todas las funciones anteriores tener la respuesta que estaban buscando. Factorial de 2 estaba diciendo retorno 2 veces el factorial de 1. Bueno, factorial de 1 devuelve 1. Así que la convocatoria de factorial de 2 puede volver 2 veces 1, y dar esa vuelta a factorial de 3, que está a la espera de ese resultado. 

Y entonces se puede calcular su resultado, 3 veces 2 es 6, y darle vuelta a factorial de 4. Y de nuevo, tenemos una video en la pila de llamadas donde esto se ilustra un poco más de lo que estoy diciendo ahora. Pero eso es todo. Esto por sí solo es la solución a calcular el factorial de un número. 

Es sólo cuatro líneas de código. Eso está muy bien, ¿verdad? Es un poco sexy. 

Así que en general, pero no siempre, una función recursiva puede sustituir a un bucle en una función no recursiva. Así que aquí, al lado del otro, es el iterativo versión de la función factorial. Ambos calcular exactamente lo mismo. 

Ambos calcular el factorial de n. La versión de la izquierda utiliza la recursividad para hacerlo. La versión a la derecha utiliza iteración para hacerlo. 

Y fíjense, tenemos que declarar una variable de un producto entero. Y luego nos bucle. Siempre y cuando n es mayor que 0, se continuar multiplicándose ese producto por n y decrementar n hasta calculamos el producto. Así pues, estas dos funciones, una vez más, hacer exactamente lo mismo. Pero ellos no lo hacen en exactamente de la misma manera. 

Ahora, es posible tener más de una base de caso o más de una caso recursivo, dependiendo en lo que su función está tratando de hacer. Usted no está necesariamente sólo limitado a un solo caso base o un solo recursiva caso. Así que un ejemplo de algo con múltiples casos base podría ser la esto- Serie de Fibonacci. 

Usted puede recordar de días de escuela primaria que la secuencia de Fibonacci se define así- el primer elemento es 0. El segundo elemento es 1. Ambos son simplemente por definición. 

Entonces se define todos los demás elementos como la suma de n menos 1 y n menos 2. Así que el tercer elemento sería 0 + 1 es 1. Y entonces el cuarto elemento sería el segundo elemento, 1, más el tercer elemento, 1. Y eso sería 2. Y así sucesivamente y así sucesivamente. 

Así que en este caso, tenemos dos casos base. Si n es igual a 1, devuelve 0. Si n es igual a 2, volver 1. De lo contrario, vuelva Fibonacci de n menos 1 más de Fibonacci de n menos 2. 

Así que eso es varios casos base. ¿Qué pasa con múltiples casos recurrentes? Bueno, hay algo llama la conjetura de Collatz. Yo no voy a decir, usted sabe lo que es eso, porque en realidad es nuestro último problema para este video en particular. Y es nuestro ejercicio para trabajar juntos. 

Así que aquí está lo que el Collatz conjetura es-- que se aplica a cada número entero positivo. Y especula que es siempre es posible volver 1 si usted sigue estos pasos. Si n es 1, para. Tenemos de nuevo a 1 si n es 1. 

De lo contrario, vaya a través de este proceso de nuevo en n dividido por 2. Y ver si puede volver a 1. De lo contrario, si n es impar, ir a través de este proceso nuevo en 3n más 1, o 3 veces N más 1. Así que aquí tenemos un caso base. Si n es igual a 1, parar. No estamos haciendo nada más recursividad. 

Pero tenemos dos casos recursivas. Si n es par, lo hacemos de un recursivo caso, llamando n dividido por 2. Si n es impar, hacemos un diferente caso recursivo en 3 veces N más 1. 

Y lo que el objetivo de este vídeo es tomar un segundo, hacer una pausa en el video, y tratar de escribir este función recursiva Collatz donde se pasa en un valor n, y calcula cuántos pasos toma para llegar a 1 si se inicia a partir de n y usted sigue estos pasos hasta arriba. Si n es 1, se tarda 0 pasos. De lo contrario, se va a dar un paso más sin embargo muchos pasos que se necesita en cada n dividido por 2 si n es par, o 3n plus 1 si n es impar. 

Ahora, me he puesto en la pantalla aquí un par de cosas de prueba para usted, un par de pruebas de casos para usted, para ver lo que estos diversos números Collatz son, y también una ilustración de los pasos que necesitan ser pasado por lo que puede suerte de ver este proceso en acción. Así que si n es igual a 1, Collatz de n es 0. Usted no tiene que ver cualquier cosa para conseguir de nuevo a 1. Usted es ya allí. 

Si n es 2, se necesita un paso para llegar a 1. Se empieza con 2. Bueno, 2 no es igual a 1. Así que va a ser un paso más sin embargo muchas medidas que adquiere n dividido por 2. 

2 dividido por 2 es 1. Así que toma un paso más sin embargo muchos pasos que tarda 1. 1 toma cero pasos. 

Para 3, como se puede ver, no hay unos cuantos pasos involucrados. Se pasa de 3. Y luego vas a 10, 5, 16, 8, 4, 2, 1. Lleva siete pasos para volver a 1. Y como se puede ver, hay una par de otros casos de prueba aquí para poner a prueba su programa. Así que de nuevo, hacer una pausa en el vídeo. Y yo iré a saltar de nuevo ahora lo que el proceso real está aquí, lo que esta conjetura es. 

A ver si puedes averiguar cómo definir Collatz de n de modo que calcula cuántos los pasos que se necesita para llegar a 1. Así que espero que, de haber detenido el video y no está a la espera de mí para darle la respuesta aquí. Pero si usted es, así, aquí está la respuesta de todos modos. 

Así que aquí está una posible definición de la función de Collatz. Nuestra base caso-- si n es igual a 1, volvemos 0. No se necesita ninguna pasos para llegar de nuevo a 1. 

De lo contrario, tenemos dos casos-- recursiva una para los números pares y otro para impar. La forma en que la prueba de números pares es comprobar si n mod 2 es igual a 0. Esto es básicamente, una vez más, hacer la pregunta, si usted recuerda lo es-- mod si dividir n por 2 hay ningún resto? Eso sería un número par. 

Y así, si n mod 2 es igual a 0 es esta prueba es un número par. Si es así, quiero regresar 1, porque este es, sin duda dando un paso más Collatz de cualquiera que sea el número es la mitad de mí. De lo contrario, quiero volver 1 más Collatz de 3 veces n más 1. Esa fue la otra paso recursivo que nos podría tomar para calcular el Collatz-- el número de pasos que se necesita para volver a 1 dado un número. Así que espero que este ejemplo Le dio un poco de una muestra de procedimientos recursivos. Con suerte, usted piensa código es un poco más hermosa si se aplican de una manera elegante, recursivo. Pero incluso si no, la recursividad es una herramienta realmente poderosa, no obstante. Y lo que es definitivamente algo para obtener su cabeza alrededor, porque usted será capaz de crear programas muy interesantes utilizando recursividad que de otra manera podría ser complejo para escribir si usted está utilizando loops y iteración. Soy Doug Lloyd. Esto es CS50.