Fibonnacci y la Recursividad
Curso de Introducción al Pensamiento Computacional con Python
Contenido del curso
La secuencia de Fibonacci es una función matemática que se define recursivamente. En el año 1202, el matemático italiano Leonardo de Pisa, también conocido como Fibonacci, encontró una fórmula para cuantificar el crecimiento que ciertas poblaciones experimentan.
Imagina que una pareja de conejos nace, un macho y una hembra, y luego son liberados. Imagina, también, que los conejos se pueden reproducir hasta la edad de un mes y que tienen un periodo de gestación también de un mes. Por último imagina que estos conejos nunca mueren y que la hembra siempre es capaz de producir una nueva pareja (un macho y una hembra). ¿Cuántos conejos existirán al final de seis meses?
Una forma de visualizar este crecimiento es mirándolo de forma tabular:
| Mes | Hembras |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 |
| 5 | 8 |
| 6 | 13 |
Un punto importante a considerar es que para el mes n > 1, hembras(n) = hembras(n - 1) + hembras(n - 2).
Como podemos ver, tenemos una definición distinta a la de factorial que vimos anteriormente. En específico, tenemos dos casos base (0 y 1) y tenemos dos llamadas recursivas (hembras(n - 1) + hembras(n - 2)).
Podemos crear una solución recursiva de manera sencilla:
def fibonacci(n): if n == 0 or n == 1: return 1 return fibonacci(n - 1) + fibonacci(n - 2)
Aunque la definición es muy sencilla, es también bastante ineficiente. En los siguientes cursos de la serie de pensamiento computacional veremos como calcular exactamente la eficiencia de este algoritmo y cómo optimizarlo. De mientras, platícanos si conoces alguna otra definición recursiva.
Marco Antonio Candia Ortega
Fredy Mendoza Vargas
Davis Álvarez
Cesar Arturo Castanon Acuna
Federico Nahuel Gonzalez
Diana Marcela Carrillo Suárez
Fabrizio Fasanando Sotelo
Jean Carlos Rodriguez
Marcos Monteverde
Carlos Eduardo Gomez García
Enzo Rafael Cárdenas Nicho
Alejandro Cuello Maure
Manuel Alejandro Hermoso
Carlos Arturo Rueda Calier
Lorenzo Enrique Piñango Cerezo
Eglantina Dani
Sergio Iván Piñón Peña
Miguel Andres Rendon Reyes
Omar Ramirez
Abrahan Javier Gamez
Alejandro Ching
Jose Flores
María Cristina Chuchón Pérez
Andrés Soret Chacin
Juan David Cepeda López
Marcos Monteverde
Antonio Demarco Bonino
Aidan Lorenzo
David Antonio Garcia Saaib
José Rodrigo Arana Hi
Iván Arcos
Bayron Danilo Ortiz Foronda
Mario Cabrera Vicencio
Mario Cabrera Vicencio
sebastian felipe herrera sanchez
Francisco Javier Aguilar Lara
Rod R
Angel Estrada
Andres Felipe Noguera Escandon
Angel Estrada
Rogger Abel Vizarreta Palomino
Vidale C.
Rogger Abel Vizarreta Palomino
Cristian Alejandro Velasco Cernas
Martin Campos
Miguel Andres Rendon Reyes
Fernando Quinteros Gutierrez
Moisés Manuel Morín Hevia
Les comparto paso a paso como entenderle al algoritmo de Fibonacci-recursividad, ya que a mi me costo bastante, espero que les sirva de referencia.
Gracias
Gracias.
🔴No esperen a la siguiente clase. 🔴 . Resuelvan sus dudas aquí: Recursion, the Fibonacci Sequence and Memoization || Python Tutorial || Learn Python Programming . Aquí la Playlist mas hardcore del mundo: Python . 🥗 ¡Éxito!
Gracias!
muy bueno, gracias
Creo que estaría bien explciar mes por mes como va evolucionando el ejercicio. En el mes 1 solo hay una hembra, esa hembra da a luz a otra hembra, por ello en el mes 2 hay 2 hembras, pero solo una de ellas fertil, por lo que la unica hembra fertil tiene 1 hembra, para el mes 3 hay 3 hembras, en este mes, la hembra del mes 1 ya vuelve a ser fertil y la que era fertil en el mes 2 ya no lo es, en el mes 3 hay 2 hembras fertiles, estas hembras dan a luz 1 hembra cada una. Por ello en el mes 4 hay 5 hembras, de las cuales 2 no son fertiles, las 3 restantes dan a luz hembra cada una y para el mes 5 hay (5+3) 8 hembras, pero solo 5 fertiles, ya que 3 de estas 8 acaban de dar a luz. Y asi sucesivamente. Espero que se entienda y que este en lo correcto. Cualquier aclaración y/o corrección es bienvenida.
Aqui te muestro en una tabla, creo que se entiende mejor, lo que tienes que saber es que: r = reproduccion n = nacimiento H = hembras M = Machos
Asmuendo las condiciones del problema
month M H 0 1 1 1 1 1 r 2 2 2 n, r 3 3 3 n, r, r 4 5 5 n, n, r, r, r 5 8 8 n, n, n, r, r, r, r, r 6 13 13 n, n, n, n. n. r, r, r, r, r, r, r, r
Para el mes 0 no pasa nada. en el mes 1 se relacionan. en el mes 2 nace una pareja que ya esta se relacionara con la anterios. en el mes 3 la r del mes 2, pasa a ser n en el mes 3, y el resto se relacionaran seran 'r' Y asi hasta completar los seis meses.
Excelente el aporte!!
Creo que la manera más fácil de entender esto es tal y como lo dice la Wikipedia: el número siguiente es la suma de los dos números anteriores:
n: El número buscado
n-1: El número anterior
n-2: El número anterior al anterior
Aunque se puede resolver con recursividad, creo que sería más fácil y tal vez más eficiente con un ciclo 🤔
✌ me ayudo tu comentario, estaba algo perdido.
Gracias
Buena idea, me puse a pensar como hacerlo y llegúe al siguiente metodo con ciclos:
def fibonacci(cantidad): # inicializamos el numero que se imprimira en uno ya que es una restriccion a = 1 # Contador de cuantos numeros se han calculado times = 0 # Variable que usaremos para guardar el numero de atras al actual b = 0 while times < cantidad: times += 1 # imprimimos el numero actual print(a) # calculamos de la siguiete forma ( el nuevo numero es la suma del actual con el numero anterior (variable b) a este, y el numero anterior cambia su valor al actual "pasado") a , b = a+b, a
la forma de asignar valores de esta forma, es como una especie de sintactic sugar:
a, b = a+b, a
El valor de a queda guardado temporalmente en otra variable y el interprete se encarga de asignarle ese valor viejo a la b.
Si no pasara esto, lo programaramos así:
temporal = a a = a + b b = temporal
La sucesión de Fibonacci en la naturaleza
!numero de conejos
Mirar este articulo esta muy interesante la sucesión de Fibonacci en la naturaleza.
muy bueno el articulo
Excelente articulo
Otros ejemplos de funciones recursivas son:
Estaría genial programarlos
Bro, ¿Tienes documentación?
Con este ejemplo sí pude entender muchas gracias
Muchas gracias!!, estaba haciendolo en mi mente de esa manera, muchas gracias!!
Este tema de recursividad me parece que la practica solamente hará que uno lo domine, pero aquí durante estas clases se nos muestra cuando una función se llama a uno mismo, pero el principio de recursividad al menos a nivel matemático es poder descomponer una operación en operaciones mas simples o también viceversa, por ejemplo si alguien te pide realizar la suma que del 21 + 22 + 23 + ....... +100, para solucionarlo lo que haríamos es un for que inicie de 21 y al final que llegue al 100 para sumarlo de manera de que sume que da como resultado 4840, dependiendo del numero de inicio y numero final serian muchas iteraciones, pero hay una manera muy fácil de hacerlo, ya que se puedes simplificarlo de la siguiente manera:
Sabemos que 100 + 21 es igual a 121, también sabemos que 99 + 22 es igual a 121, y que 98 +23 es igual a 121
Este resultado se repite y dará el mismo resultado, entonces podemos predecir que los números centrales de la suposición anterior darán 121, por lo que podemos decir que esta operación se repetirá 40 veces que es la mitad de los ciclos que haría el for por lo tanto podemos ahorrarnos el for y hacer la siguiente simple operación (21 + 100) * 40 = 21 + 22 + 23 ......+ 100.
total = 0 limite_inf = int(input("Escribe el valor en donde comenzara la sumatoria: ")) limite_sup = int(input("Escribe el valor final que sumara la suma")) for numero in range(limite_inf, limite_sup): total += numero print(numero) print(total) repeticiones = (limite_sup - limite_inf)/2 print(repeticiones) resultado_simplificado = (limite_sup + limite_inf - 1)*repeticiones print(resultado_simplificado)
Esto siempre y cuando las repeticiones sean pares aunque para las impares solo se necesita eliminar el ultimo numero para tener una repetición par poder hacer la operación simple, y el resultado sumarle el excedente para tener el resultado correcto.
buen ejemplo!
Muy muy buen ejemplo 👍👍
Para poder entenderlo un poco mejor, use ambas maneras, en iteración y en recursividad:
Gracias!!"
Con este video terminé de entender la Secuencia Fibonacci: https://www.youtube.com/watch?v=DKGsBUxRcV0
Gracias por el video amigo me ha ayudado a entender la sucesion
explicacion mas bonita haciendo clic aqui Imagina que agregamos el numero 1 Entraría en el if por lo tanto hasta ahí llegaría nuestro programa
Si elegimos el numero 2
Se brinca el if porque pues no cuenta, y se va directo al return que llama directo a la función, por lo que obtenemos el primer atributo del return fibonacci(2 - 1), y como es igual a 1, retornamos el 1. el segundo punto es fibonacci(n - 2) por lo que su respuesta es 0 al volver a la función, pero en la condición vemos que si es 0 retorna un 1. es decir que al momento de retornar tenemos 1 + 1.
Si elegimos el numero 3
Entramos a la función con n=3, por lo que nos brincamos el if, el primer resultado del retorno es fibonacci(3 - 1), es decir que volvemos a entrar la función con fibonacci(2), por lo que nos brincamos el if y nos vamos al return. Espero te hayas dado cuenta, obtenemos el resultado de si hubiéramos elegido el numero dos, si no te queda claro sigue los pasos de arriba donde dice 'si elegimos el numero 2'.
El chiste que de la línea return ya tenemos el primer termino que es 1+1 que es igual a fibonacci(2). Ahora calculamos el otro numero fibonacci(3-2) que seria igual a fibonacci(1) por lo tanto seria igual a 1.
Por si acaso te dire qué está pasando aqui, el return principal se encarga de hacer una lista de sumas de puros digitos 1.
Es decir que tu al buscar el fibonacci de algún numero, el resultado es la suma de 0+1 n veces.
Un ejemplo mas: tu al buscar el fibonacci de 6 su resultado será el return que llamo a la misma función 13 veces sumando 1+1+1+1+1+... hasta obtener 13. Cada iteración sumó un 1 al resultado
Si elegimos el numero 4 Este ejemplo será mas gráfico
fibo(4) = fibo(4-1) + fibo(4-2) = fibo(3) + fibo(2) = (fibo(3-1) + fibo(3-2)) + (fibo(2-1) + fibo(2-2)) = (fibo(2) + fibo(1)) + (fibo(1) + fibo(0)) = ((fibo(2-1) + fibo(2-2)) + fibo(1)) + (fibo(1) + fibo(0)) = ((fibo(1) + fibo(0)) + fibo(1)) + (fibo(1) + fibo(0)) = ((1 + 1) + 1) + (1 + 1)) = 1 + 1 + 1 + 1 + 1 = 5
def fibonacci(n): print(n) if n == 0 or n == 1: return 1 return fibonacci(n - 1) + fibonacci(n - 2) n = int(input('Ingresa un numero: ')) print(f'El numero final fibonacci es {fibonacci(n)}')
muchas gracias, ahora lo comprendo mejor.
Cómo opera la serie de Fibonacci:
Genera el número siguiente agregando dos números anteriores. Es decir, comienza con dos números: F0 y F1. Los valores iniciales de F0 y F1 se pueden tomar 0, 1 o 1, 1 respectivamente.
Se tienen que cubrir las siguientes condiciones:
Fn = Fn-1 + Fn-2
Hola a todos, es importante tener en cuenta que la sucesión de fibonacci siempre inicia en F0 = 0, matemáticamente la definición de recurrencia esta dada por:
Se puede leer un poco más en la Wiki. Con la anterior definición de recurrencia se implementa el algoritmo recursivo en Python o en cualquier otro lenguaje que les guste. Este fue el que implementé en código Python:
def fibonacci(n): """Calcula el n-esimo elemento sucesión fibonacci. params: n: int -- n-esimo elemento return: fibonacci(n): int """ if n < 2: return n return fibonacci(n - 1) + fibonacci(n - 2)
Aclarar que para el ejemplo que da el profesor David, referente a los conejos, se puede crear confusión ya que para este problema al mes 0, se tiene 1 pareja de conejos. Luego en el mes 1 esta pareja de conejos se cruza, pero aún sigue existiendo la misma pareja (1 pareja de conejos).
Finalmente para el mes 2 la pareja da a luz otra pareja de conejos, entonces ya se tienen 2 parejas y nuevamente la pareja que ya existía vuelve a cruzarse y así continúa el ciclo.
Espero sea útil el aporte. Un saludo a todos.
Uff gracias, ahora lo entiendo mucho mejor
Muchas gracias!
Mi código:
def main(): def fibonacci(n): # print(n) if n==0 or n==1: return 1 return fibonacci(n-1)+fibonacci(n-2) print('Sucesion de fibonacci') numero = int(input('Introduce cuantos numeros de fibonacci quieres generar: ')) for i in range(numero): print(i,fibonacci(i)) if __name__ == "__main__": main()
y lo que regresa:
Sucesion de fibonacci Introduce cuantos numeros de fibonacci quieres generar: 20 0 1 1 1 2 2 3 3 4 5 5 8 6 13 7 21 8 34 9 55 10 89 11 144 12 233 13 377 14 610 15 987 16 1597 17 2584 18 4181 19 6765
Tengo una pregunta. Para que agregas este IF, Que utilidad tiene? if name == "main": main()
Es como se define el inicio de un programa de python y es donde inicia cuando se ejecuta en la terminal. Para mayor detalle, te recomiendo realizar el curso básico de python, es buenísimo y Facundo (el profesor) lo explica super bien. Saludos y éxito!
Así para imprimir una determinada cantidad de números de la serie
def fibonacci(n, i=0, j=1): print(i+j) return fibonacci(n-1, i+j, i) if n > 1 else 0 if __name__ == '__main__': fibonacci(int(input('Cuantós número de la serie desea imprimir?: ')))
¡Genial! Piensa qué tal que alguien anda de curioso y cambia el main, eso le daria acceso a cambiar i e j!!!! y eso desploma la función, para evitar eso, yo pondría i=0 y j=1 dentro de la función porque así como preparámetros, el usuario podría combiarlos cuando llama la función, claro, para ello debe de modificar main pero uno nunca sabe. El usuario es muy curioso jajaja
Claro, pero dejarlo como parametros da apertura a que se formen nuevas series según lo que se necesite, que el usuario sea muy curioso está muy bien.
Si no entendieron muy bien de qué va pueden echarle un vistazo a este video:
https://www.youtube.com/watch?v=k6I_TOW6O2o&ab_channel=KhanAcademyEspa%C3%B1ol
La sucesión de Fibonacci es la sucesión de números que, empezando por la unidad, cada uno de sus términos es la suma de los dos anteriores (1,1,2,3,5,8,13,…).
Quieren ver una canción de esto de dos minutos? vean al
¡Muy buen aporte umi! 🤟 Recuerda clasificar tus aportes y preguntas de manera correcta para tener un curso y plataforma ordenada 😉
