Fibonnacci y la Recursividad

19/31

Lectura

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.

...

Reg铆strate o inicia sesi贸n para leer el resto del contenido.

Aportes 180

Preguntas 2

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

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.

馃敶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!

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.

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 馃

Otros ejemplos de funciones recursivas son:

  1. Tri谩ngulo de Pascal (la dsposici贸n de n煤meros tales que cada fila corresponde a los coeficientes del binomio (a+b)^n donde n representa el numero de filas. La fila n se obtiene de la fila n-1, Rn(i)=Rn-1(i-1)+Rn-1(i) ).
  2. Polinomios de Hermite (los polinomios de Hermite de orden n>2 se pueden expresar en t茅rminos de los dos primeros polinomios H0(x) y H1(x), Hn(x) = 2x*Hn-1(x) - 2(n-1)Hn-2(x) )

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.

Para poder entenderlo un poco mejor, use ambas maneras, en iteraci贸n y en recursividad:

Con este video termin茅 de entender la Secuencia Fibonacci:
https://www.youtube.com/watch?v=DKGsBUxRcV0

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 鈥榮i 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)}')

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.

  • Inicio Mes 0: Tengo 1 pareja conejos (Pareja A).
  • Mes 1: Pareja de conejos A se cruzan. A煤n tengo 1 pareja de conejos.
  • Mes 2: Pareja de conejos A da a luz otra pareja B, y vuelven a cruzarse pareja conejos A. Ahora tengo 2 parejas A y B.
    .
    .
    .
    y as铆 contin煤a el ciclo. As铆 que para una implementaci贸n correcta de Fibonacci, debe utilizarse la definici贸n matem谩tica de recurrencia que mostr茅 al inicio, ya que lo referente a los conejos es una forma de explicar la sucesi贸n.

Espero sea 煤til el aporte. Un saludo a todos.

En este video se da una excelente explicaci贸n de esta clase y la pasada. Espero les sirva.

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

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?: ')))

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帽ol

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,鈥).

Les comparto mi c贸digo que imprime la secuencia fibonacci hasta el n煤mero que elijan

<numero = int(input ('escoge un n煤mero para la secuencia fibonacci: \n'))

i = 0
    
def fibonacci (num):
    """
    Devuelve el valor del numero para la serie fibonacci
    numero int > 0
    returns secuencia fibonacci
    """
    if num == 0 or num ==1:
        return 1
    return fibonacci(num-1) + fibonacci (num-2) 

print ('Puesto', 'Valor')
while (i < numero):
    print (i,'    ', fibonacci (i))
    i = i + 1>

E imprime como resultado lo siguiente:

<escoge un n煤mero para la secuencia fibonacci: 
10
Puesto Valor
0      1
1      1
2      2
3      3
4      5
5      8
6      13
7      21
8      34
9      55>

Sucesi贸n de Fibonacci
Es una serie matem谩tica infinita, donde:
0 1 1 2 3 5 8 13 21 鈥
Donde la suma de los dos n煤meros anteriores da el resultado del
Numero actual
A=5
B=8
A + B = 13
C=13
B + C = 21
D=21

Gracias!

def fibonnacci(n):
    if (n == 1 or n == 0):
        return 1

    return fibonnacci(n-1) + fibonnacci(n-2)


numero = int(input('Ingrese la cantidad de numeros a generar : '))

for i in range(numero+1):
    print(f'Num {i} ==> {fibonnacci(i)}')

Conozco otra definici贸n de recursividad llamada Recursi贸n de Cola o Tail Recursion que es un mecanismo que permite tener funciones recursivas sin temer por posibles desbordamientos de pila. A diferencia de la recursividad cl谩sica, donde cada llamada recursiva implica la creaci贸n de un nuevo frame en la pila de llamadas (con el riesgo de desbordamiento), con el tail recursion es posible realizar dichas llamadas recursivas reaprovechando el frame de pila anterior y evitando as铆 el desbordamiento.

Ejemplo Tail Fibonacci

def tail_fibonacci(n, a = 0, b = 1): 
    if n == 0:
        return a
    if n == 1: 
        return b
    return tail_fibonacci(n - 1, b, a + b)

def fibonacci(n):
    return tail_fibonacci(n)

n = int(input("Digite un n煤mero: "))
print(f'Por recusi贸n de cola fibonacci {n} es {fibonacci(n)}')

La recursividad tambien sirve para probar cosas.
Existe algo llamado inducci贸n matematica, sirve para probar si una form煤la, teorema o afirmaci贸n es verdadera.
La inducci贸n matematica usa recursividad, ejemplo:
Dada la siguiente sumatoria, prueba que la form煤la es verdad para n >= 1

def sumatoria(n):
	if n == 1:
		return 1
	return n + sumatoria(n - 1)

Ac谩 dej贸 la soluci贸n con recursividad y con un bucle for ya que la recursividad no es la soluci贸n 贸ptima para resolver este problema por la complejidad algor铆tmica que representa.

def fibonacci(n):
    """Calcula el fibonacci por recursion 
    
    Params:
        n: int

    Return:
        fibonacci(n) : int
    """
    if n == 0 or n == 1:
        return 1

    return fibonacci(n-1) + fibonacci(n-2)

def fibonaccifor(n):
    """Calcula el fibonacci por bucle for 
    
    Params:
        n: int

    Return:
        b: int
    """
    a = 0
    b = 1
    
    for i in range(n):
        c = a + b
        a = b
        b = c

    return b

def run():
    n = int(input('Ingresa un numero: '))
    print(fibonaccifor(n))


if __name__ == '__main__':
    run()

Algo que deber铆a ser mencionado es que hay maneras de optimizar la recursividad. Ya que el problema de la recursividad es que al realizar c谩lculos con un n lo suficientemente grande, la funci贸n recursiva se llama as铆 misma hasta llegar a la 煤ltima llamada y luego se devuelve.

Dejo a continuaci贸n un programa de recursividad de Fibonacci.Sugiero utilizar para este programa n = 412, ya que pasaran minutos y a煤n su equipo no habr谩 realizado el c谩lculo.

# Autor:
#   Sergio Carrillo
#   @SergioAmaro_

# 脷ltima fecha de modificaci贸n:
#   29/01/2021

def fibonacci(n):
  """Calcula Fibonacci(n) mediante recursi贸n por cola

  Args:
      n ([int]): [n>=0]

  Returns:
      [int]: []
  """
  a, b = 0, 1
  
  if n == 0: 
    return a
  elif n == 1: 
    return b
  elif n > 1: 
    return fibonacci(n-1) + (fibonacci(n-2))


def main():
  n = int(input('Ingresa un n煤mero entero: '))
  print(fibonacci(n))

if __name__ == '__main__':
  main()

Por otra parte existe la recursividad por cola, y esta nos permite ir acumulando el c谩lculo sin necesidad de esperar llegar a la 煤ltima llamada de la funci贸n para devolverse. Sugiero investigar:

Dejo a continuaci贸n un programa que plantea el mismo ejercicio solucionando con recursividad por cola. Pueden calcular Fibonacci(412) y el c谩lculo ser谩 en cuesti贸n de segundos. En comparaci贸n al programa anterior, plantear soluciones con este m茅todo es mucho m谩s eficiente en t茅rminos de recursos.

# Autor:
#   Sergio Carrillo
#   @SergioAmaro_

# 脷ltima fecha de modificaci贸n:
#   29/01/2021

def tailFibo(n):
  """Calcula Fibonacci(n) mediante recursi贸n por cola

  Args:
      n ([int]): [n>=0]

  Returns:
      [int]: []
  """
  a, b = 0, 1
  def go(n, a, b):
      if n == 0: return a
      elif n == 1: return b
      elif n > 1: return go(n-1, b, a+b)

  return go(n, a, b)


def main():
  n = int(input('Ingresa un n煤mero entero: '))
  print(tailFibo(n))

if __name__ == '__main__':
  main()

#Hola Chic@s pueden practicar con el projecto Euler he aqui un ejemplo

#Problem 2
"""Each new term in the Fibonacci sequence is generated by adding the previous two terms.
By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million,
find the sum of the even-valued terms."""

x = [1, 2]
Number_final = int(input('How many numbers do you want ?'))
#Which_number = int(input('Which number of the list do you want? '))

for i in range(Number_final):
	x.append(x[-1]+x[-2])
	i += 1
#print(x[Which_number])
total = 0
#Now we will get the even summ 
for i in x:
	if i % 2 ==0:
		total = total + i
print(total)

Una explicaci贸n gr谩fica respecto al tema:

馃捇Por si alguien lo necesita para futuras referencias, les dejo el Python Visualizer para ver como se comporta nuestro codigo. 馃榿馃榿馃榿馃榿馃榿馃榿
http://www.pythontutor.com/visualize.html#mode=edit 馃捇

Les dejo varias formas de implementar fibonacci (no document茅 las funciones)

from functools import lru_cache
import time

def fibonacci(n):
    if n == 0 or n == 1:
        return 1

    return fibonacci(n - 1) + fibonacci(n - 2)

@lru_cache(maxsize = 1000)
def fibonacci_lru(n):
    #Check that the input is a positive integer
    if type(n) != int:
        raise TypeError("n must be a positive int")
    if n < 1:
        raise ValueError("n must be a positive int")

    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n > 2:
        return fibonacci(n-1) + fibonacci(n-2)
    
#Using memoization
fibonacci_cache = {}

def fibonacci_memo(n):
    #If we have cached the value, return it
    if n in fibonacci_cache:
        return fibonacci_cache[n]

    #Compute the Nth term
    if n == 1:
        value = 1
    elif n == 2:
        value = 1
    elif n > 2:
        value = fibonacci(n-1) + fibonacci(n-2)

    #Cache the value and return iter
    fibonacci_cache[n] = value
    return value


def run():
    n = int(input("Cantidad de elemento de la sucesi贸n: "))
    opcion = int(input("""Ingresa la opci贸n:
                       1. Fibonacci (normalito)
                       2. Fibonacci (decoradores)
                       3. Fibonacci (Memoization)
                       """))
    inicial = time.time()
    if opcion == 1:
        for i in range(1, n+1):
            print(f'Elemento {i}: {fibonacci(i)}')
        print(f"Tiempo: {time.time()-inicial}")
    elif opcion == 2:
        for i in range(1, n+1):
            print(f'Elemento {i}: {fibonacci_lru(i)}')
        print(f"Tiempo: {time.time()-inicial}")
    elif opcion == 3:
        for i in range(1, n+1):
            print(f'Elemento {i}: {fibonacci_memo(i)}')
        print(f"Tiempo: {time.time()-inicial}")
    else:
        print("Es de 1 a 3. (鈺扳枴掳锛夆暞锔 鈹烩攣鈹")
        

if __name__ == '__main__':
    run()

Recuerden que el primer paso para entender la recursividad es entender la recursividad

Aqui tienen un video donde explican, el metodo fibonacci de forma iterativa y recursiva es excelente tambien:

https://www.youtube.com/watch?v=4zFoXA8D8pA&ab_channel=MidiarioPython

Si alguno tiene dudas en cuanto al algoritmo de fibonacci esta explicacion esta muy buena y me ayudo a comprender mejor : https://www.youtube.com/watch?v=6_Y-2-50SSA

Hola , este es mi ejercicio de la sucesion fibonacci , lo entendi mejor de esta manera

def fibonacci():
    n = int(input('ingresa un numero de secuencia: '))

    num1, num2 = 0, 1  # caso base
    print(f'{num1}')
    print(f'{num2}')
    for i in range(n):
        num3 = num1+num2
        print(f'{num3}')
        num1 = num2  # 1
        # print(num1)
        num2 = num3  # num1+num2 1
       # print(num2)


fibonacci()```
# Function for nth fibonacci number - Space Optimisataion 
# Taking 1st two fibonacci numbers as 0 and 1 
  
def fibonacci(n): 
    a = 0
    b = 1
    if n < 0: 
        print("Incorrect input") 
    elif n == 0: 
        return a 
    elif n == 1: 
        return b 
    else: 
        for i in range(2,n): 
            c = a + b 
            a = b 
            b = c 
        return b 
  
# Driver Program 
  
print(fibonacci(9)) 
  

Hola amigos,
Buscando encontr茅 esta otra definici贸n recursiva, se trata de la sucesi贸n de Lucas
Se definde la siguiente maner:

Y los resultados que se deber铆an obtener son los siguientes:

Lo implemente en Python (ya quisiera graficarlo), y ac谩 les comparto el c贸digo:

def sucesion_lucas(numero):
    #print(numero) 
    if numero == 1:
        return 2
    elif numero == 2:
        return 1
    else:
         return sucesion_lucas(numero - 1) + sucesion_lucas(numero - 2)
    
numero = int(input('Un numero: '))
print(sucesion_lucas(numero))

馃槂

Hay veces en problemas de f铆sica cu谩ntica, que aparecen ciertas funciones especiales, ciertos polinomios bonitos que contienen relaciones de recurrencia, que son, b谩sicamente, relaciones recursivas, esto nos permite resolver un problema cu谩ntico de manera computacional de modo eficiente, para m谩s informaci贸n, investiguen sobre los polinomios de Hermite o Lagrange 馃槃

Una problema que se da soluci贸n con recursividad es el famoso problema de las torres de hannoi.
Aqu铆 les dejo un video donde explica que son las torres de hanoi.
https://www.youtube.com/watch?v=LM68IQvIo_E

鈥淓n los siguientes cursos de la serie de pensamiento computacional veremos como calcular exactamente la eficiencia de este algoritmo y c贸mo optimizarlo鈥
.

As铆 es como yo entiendo la recursividad en esta funci贸n:
![](
H谩ganme saber si me equivoqu茅 en algo 鉂わ笍

Usando recursividad y m谩s eficiente que el ejemplo de la clase:

def serie_fibonacci(cantidad_meses, mes=0, a=1, b=0):
    if mes <= cantidad_meses:
        print('Mes:', mes, '->', a + b)
        serie_fibonacci(cantidad_meses, mes + 1, b, a + b)


def main():
    print('Serie Fibonacci')
    mes = int(input('Digite la cantidad de meses: '))
    serie_fibonacci(mes)


if __name__ == "__main__":
    main()

Salida en pantalla para 10 meses:

Serie Fibonacci
Digite la cantidad de meses: 10
Mes: 0 -> 1
Mes: 1 -> 1
Mes: 2 -> 2
Mes: 3 -> 3
Mes: 4 -> 5
Mes: 5 -> 8
Mes: 6 -> 13
Mes: 7 -> 21
Mes: 8 -> 34
Mes: 9 -> 55
Mes: 10 -> 89

Otro ejemplo de llamada recursiva es el algoritmo de m谩ximo com煤n divisor:

def maximo_comun_divisor (m, n):
    """
    Calcula el maximo com煤n divisor de m y n.
    m >= n > 0
    return maximo_comun_divisor.
    """
    if n == 0:
        return m
    return maximo_comun_divisor (n, m % n)

n = int(input('Escoge un n煤mero entero: '))
m = int(input('Escoge un n煤mero entero: '))

print(maximo_comun_divisor(m, n))```

En algunas fuentes de informaci贸n les saldr谩 que fibonacci es 0, 1, 1, 2, 3, 5, 8, 13 y no 1, 1, 2, 3, 5, 8, 13
Esto es muy confuso aveces.
En aplicaciones donde tienen retos de programaci贸n les saldr谩 con el 0 y para solucionar este inconveniente en el c贸digo es cambiar el return = 1 por return = n:

def fibonacci(n):
    If n == 0 or n == 1:
        return n

    return fibonacci(n - 1) + fibonacci(n - 2)```

馃槃 Por si se lo preguntaban aqu铆 est谩 la c贸mo calcular e imprimir los n煤meros de la serie de Fibonacci:

def fibonacci(n):

    if n <= 1:
        return n
    else:
        return(fibonacci(n - 1) + fibonacci(n - 2))


n = int(input('Escribe hasta que n煤mero se calcular谩 la serie de Fibonacci: '))
for i in range(n+1):
    print(fibonacci(i))

Ser铆a bueno corregir varios detalles en este ejercicio que no llevan a la soluci贸n correcta. Se pudo haber elegido un ejemplo m谩s natural y menos complicado.
鈥 por si alguien escribe un valor negativo, se requiere una validaci贸n extra

def fibo(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fibo(n - 1) + fibo(n - 2)

La sucesi贸n de Fibonacci y la raz贸n a煤rea.
https://www.youtube.com/watch?v=yDyMSliKsxI
Un v铆deo muy interesante con la ciencia que hay detr谩s de esta sucesi贸n.

Hace 10 a帽os me dejaron de tarea hacer la secuencia de Fibonacci pero en Java, encontr茅 el ejercicio y lo transform茅 a Python, jaja
Obvio no es la mejor soluci贸n pero se las quer铆a compartir

As铆 para que el usuario pueda elegir el mes del c谩lculo.

def fibonacci(n):
    if n == 0 or n == 1:
        return 1

    return fibonacci (n - 1) + fibonacci (n - 2)

n = int(input("Escriba el mes que desea conocer: "))
print (f'En el mes n煤mero {n} habr谩n {fibonacci(n)} conejos')```

Esto debi贸 hacer sido un video

Aqui un ejemplo con sumatoria.

def sumatoria(n):
""鈥淐alcula la sumatoria de n.
n int>=0
returns sumatoria(n)
鈥""
if n == 1:
return 1
return n + sumatoria(n - 1)
n= int(input('Escribe un entero: '))
print(sumatoria(n))

Quedo claro!! 鈥 a la espera de ver como optimizar c贸digo.

Buena herramienta, solo que si me cuesta un poco entender en que casos pr谩cticos o mas complejos usarlo.

La tabla en la que se describe el comportamiento de crecimiento para la camada de conejos esta mal, deber铆an corregirlo, pero si gustan corroborar, pueden usar espec铆ficamente la ecuaci贸n descrita de forma manual para descubrir los valores por mes que deber铆a estar en la tabla.

Por ejemplo si: mes n > 1
tomamos el mes numero 2 y reemplazamos en la formula

F(n) = (n-1)+(n-2)
F(2) = (2-1)+(2-2)
entonces
F(2) = 1

que quiere decir esto, que como bien comprende el planteamiento del problema en el primer mes no vamos a encontrar hembras debido a que debe pasar un mes para que la primera hembra pueda tener una nueva pareja de conejos, por lo tanto en el mes 0 tenemos 0 hembras, eso quiere decir que los valores est谩n desajustados por un mes entero de calculo.

Bueno al menos creo que es as铆.

si estoy mal espero alguien me pueda ayudar.

B谩sicamente una definici贸n recursiva es cualquier funci贸n que tenga una variable que est茅 cambiando de valor en cada iteraci贸n, entend铆 bien?

Tengo duda acerca del c贸digo del ejemplo:

def fibonacci(n):
    if n == 0 or n == 1:
        return 1

    return fibonacci(n - 1) + fibonacci(n - 2)

驴No deber铆a ser?:
if n == 0 o n == 1:
return n

Esto es un peque帽o aporte sobre Fibonacci

def fibonacci(n):
    resultado = 0
    res = 0
    for i in range(1, n+1):
        if i == 1:
            res1 = 0
            res2 = 0
            resultado = 0
        elif i <= 3:
            res1 = 0
            res2 = 1
            resultado = 1
        else:
            res = res1 + res2
            res2 = res1
            res1 = res
            resultado = resultado + res
    return(resultado)

print(fibonacci(3))

Hola, yo tenia un poco de problemas para entender la recursividad, pero encontr茅 estas diapos que explican de manera gr谩fica la recursividad. A mi me sirvi贸 mucho, espero a alguien le sirva tambi茅n. Saludos :3

Si necesitan reforzar el concepto de recursividad, pueden ver este video, aqu铆 vas a apreciar los mismos ejemplos que se presentan en este curso

La recursividad de manera gr谩fica. Espero pueda ayudar a alguien a entender un poco mejor lo que sucede.

Aqui dejo una funcion para calcular el n-simo numero de Fibonacci mejor optimizada

def fibonacci(n):
    n1, n2 = 0, 1
    for i in range(n-1):
        aux = n1 + n2
        n1 = n2
        n2 = aux
    return n2

Aqu铆 os dejo otra funcion que retorna una lista con los numeros de Fibonacci hasta el n-simo.
Lo logra mediante la memoizacion.
鈥淓n Inform谩tica, el t茅rmino memoizaci贸n (del ingl茅s memoization) es una t茅cnica de optimizaci贸n que se usa principalmente para acelerar los tiempos de c谩lculo, almacenando los resultados de la llamada a una subrutina en una memoria intermedia o b煤fer y devolviendo esos mismos valores cuando se llame de nuevo a la subrutina o funci贸n con los mismos par谩metros鈥 (https://es.wikipedia.org/wiki/Memoizaci贸n)

def memo_fibonacci(n, memo=None):
    if memo == None:
        memo = [0, 1, 1, 2]
    
    for i in range(n+1):
        if i > len(memo)-1:
            memo.append(memo[i-1] + memo[i-2])
        else:
            continue

    return memo

La sucesi贸n de gradiente combinatorio es otro ejemplo de recursividad.

La f贸rmula es: Nn+1 = Cn + Rn

A partir de ella se pueden obtener las dos siguientes:

Rn = Nn+1 鈥 Cn ; Cn = Rn+1 鈥 Rn

A partir de una demostraci贸n se obtiene que Nn+1 = Rn+1
Debido a lo cual, la f贸rmula Cn = Rn+1 鈥 Rn se puede reescribir de la siguiente forma: Cn = Nn+1 鈥 Rn

Donde:

Nn+1: N煤mero de combinaciones dobles sin repetici贸n y/o permutaci贸n. El sub铆ndice n representa la cantidad de colores y/o dise帽os pertenecientes a determinado conjunto, y es un n煤mero natural a partir de cero. Aunque, en ese caso, obviamente no habr铆a ning煤n resultado de alguna combinaci贸n doble, pues N0+1 = N1 = 0, esto, por el hecho de que la sucesi贸n de gradiente combinatorio solamente toma en cuenta las combinaciones dobles, es decir, las que se pueden agrupar en pares o de dos en dos, obtenidas, como m铆nimo, de entre un conjunto formado por dos o m谩s elementos. A modo de ejemplo, N1+1= N2, se lee as铆: el n煤mero de combinaciones dobles sin repetici贸n y/o permutaci贸n entre los elementos de un conjunto formado por dos colores o dise帽os es igual a鈥 as铆 correspondientemente.

El factor positivo +1 significa que, con cada suma obtenida con los sumandos Cn + Rn, se encuentra la cantidad total de combinaciones sin repetici贸n y/o permutaci贸n del siguiente conjunto de colores y/o dise帽os, siempre y cuando este aumente en la cantidad de uno respecto al anterior (ver tabla 9). Por patr贸n, se tiene que: N1 = C1 + R1 = R2 ; N2 = C2 + R2 = R3 ; N3 = C3 + R3 = R4 , y as铆 sucesivamente; por lo que la f贸rmula desarrollada es la siguiente: Nn+1 = Cn + Rn . En consecuencia, se cumple con la siguiente condici贸n: Nn+1 = Rn+1

Cn: Cantidad de colores o dise帽os de un conjunto. Para facilitar los c谩lculos se recomienda asignar n煤meros naturales consecutivos a cada conjunto de colores y/o dise帽os, como se observa en la columna izquierda de la tabla 9.

Rn: Resultado de la cantidad de combinaciones dobles sin repetici贸n y/o permutaci贸n entre los elementos de Cn.

Colores o dise帽os N煤mero de combinaciones
C1=1 R1=0
C2=2 R2=1
C3=3 R3=3
C4=4 R4=6
C5=5 R5=10
C6=6 R6=15
C7=7 R7=21
C8=8 R8=28

**Nota:
En este ejemplo se usa la f贸rmula de gradiente combinatorio para colores y/o dise帽os de ropa pero se puede aplicar para conjuntos formados por otros tipos de elementos.
**

def run():
    pass


def fibonacci(n):
    if n == 0 or n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)
n = int(input("Ingrese un Numero: "))
print(f' El fibonacci de {n} es {fibonacci(n)}')

if __name__ == '__main__':
    run()

Otra de las funciones recursivas que existen en las matem谩ticas es el determinante de una matriz por el m茅todo de cofactores y uno de mis m茅todos de ordenamiento favoritos igual se logra con recursividad: Ordenamiento Quicksort.

def fibonacci(n):
if n0 or n1:
return 1

return fibonacci(n-1) + fibonacci(n-2)

n = int(input('En cu谩l mes desea saber: 鈥))
print(f鈥橢n el mes {n} habr谩 {fibonacci(n)} conejos鈥)

Genial realice una peque帽a modificaci贸n al c贸digo.

def fibonacci(n):
    if n == 0:
	return 1
    elif n < 4:
        return n
    else
       return fibonacci(n - 1) + fibonacci(n - 2)

Muy interesante y fundamental, aqu铆 un video para poder ampliar y entender un poco m谩s

https://www.youtube.com/watch?v=sY0HYpU2cwk


def fibonacci():

    """ Serie Fibonacci
    recibe un numero entero

    """
    n = int(input('Digite un numero entero'))

    a =0
    b=1

    for i in range(n):

        print(a)

        c=a+b
        a=b
        b=c

if __name__ =='__main__':
    
    fibonacci()

Entend铆 el funcionamiento c贸digo y como funciona Faccionario
Lo que no entiendo es la formula de fibonacci(n-1) + fibonacci(n-2). Ayuda

def fibonacci(n):
    if n < 2:
        return n
    else:
        return fibonacci(n-2) + fibonacci(n-1)


if __name__ == '__main__':
    n = int(input('Dame un numero para calcular: '))
    for i in range(n):
        print(fibonacci(i+1))

Dice que los conejos se pueden reproducir hasta la edad de 1 mes. Mas adelante dice que la hembra siempre es capaz de producir una nueva pareja. Entiendo el concepto de fibonacci pero el ejemplo lo encuentro confuso. Quiz谩s no lo entend铆 bien simplemente pero aprovecho de manifestar mi inquietud.

Asi fue como hice para poder ver todos los numeros de la serie y no solo uno

def fibonachi(n):

   
    if n <=1:
        return n

    else:
        return fibonachi(n-1) + fibonachi(n-2)

    
print('驴 T E  F I B O N A C H E O   U N   N U M E R O ?')
n = int(input('Dime el numero:'))


while n >=1:
    print(fibonachi(n))
    n -= 1```

def fibonacci(n): 
    """Calcula la seria fibonacci 
    """
    
    if n == 0 or n == 1: 
        return 1 

    return fibonacci(n - 1) + fibonacci(n - 2)  

n = int(input('Escribe un entero: '))

print(fibonacci(n)) 


 

Yo uso esta funci贸n recursiva para obtener un n煤mero desde la consola, y mientras haya un error en el dato ingresado, vuelve a ejecutarse

def get_number():
    try:
        return int(input('Ingresa un n煤mero: '))
    except:
        return get_number() 

Al principio no sabia que hacia mi funcion, me toco volver a lapiz y papel para saber que estaba haciendo

def fibonacci(n):
    if n == 0 or n == 1:
        return 1

    return fibonacci(n - 1) + fibonacci(n - 2)

fibonacci(5)

Que interesante hab铆a escuchado hablar sobre la secuencia de Fibonnacci pero nunca se me ocurri贸 que se podr铆a llegar a utilizar en programaci贸n.

Cuenta regresiva hasta cero a partir de un n煤mero

def cuenta_atras(num):
num -= 1
if num > 0:
print(num)
cuenta_atras(num)
else:
print(鈥淔in de la funci贸n鈥, num)

cuenta_atras(5)

Sumatoria de n煤meros naturales desde 1 hasta n:

Ac谩 mi c贸digo

def fibonacci(n):
    """Calcula el la secuencia de fibonacci de n

        n int > 1
        returns (n - 1) + (n -2)
    """
    print(n)
    if n == 0 or n == 1:
        return 1

    return fibonacci(n - 1) + fibonacci(n - 2)

if __name__ == '__main__':
    n = int(input('Escriba un entero: '))

    print(fibonacci(n))
def fibonacci(n):
    """Calcula la secuencia fibonacci de n

    n int > 1
    returns (n-1) + (n-2)
    """
    print(n)
    if n == 1 or n == 0:
        return 1

    return fibonacci(n - 1) + fibonacci(n - 2)

n = int(input('Escribe un entero: '))

print(fibonacci(n))```
<h1>Basic Algorithm</h1>
def fibinacci(x,y,z,fin):
    while z < fin:
        print(z)
        z = x + y
        x = y
        y = z        

number = int(input('Ingresa final de finacacci: '))
fibinacci(x=0,y=1,z=1,fin=number)
def fibonacci(number):
    """
        Calcular el factorial de la variable n

        number int > 0
        retrurn number factorial
    """
    print(number)
    if number == 0 or number == 1:
        return 1

    return fibonacci(number - 1) + fibonacci(number - 2)


if __name__ == '__main__':
    number = int(input('Escribe un n煤mero: '))

    result = fibonacci(number)

    print('La serie Fibonacci de {} es {}'.format(number, result))

Esta es una funcion que hice pero mas concreta al tema de los conejos, espero puedan comentar que les parece

def calc_female_rabbit_population(rabbits, total_months, current_month = 0, reprod_rabbits = 0):
    """Calcula la populacion de conejas en un lapso de tiempo

    rabbits int cantidad de conejos > 0
    total_months int lapso de tiempo en meses
    current_month int el mes actual
    reprod_rabbits int conejas que pueden reproducirse
    """
    current_status = [f"Month {current_month} with {rabbits} rabbits"]
    if current_month == total_months:
        return current_status
    else:
        new_rabbits = reprod_rabbits + rabbits if reprod_rabbits > 0 else 1
        new_reprod_rabbits = reprod_rabbits + (rabbits - reprod_rabbits)
        return current_status + calc_female_rabbit_population(new_rabbits, total_months, (current_month + 1), new_reprod_rabbits)

results = calc_female_rabbit_population(1, 6)
for result in results:
    print(result)

Me encanta la aplicabilidad en todas las 谩reas de la vida de esta secuencia Y a nivel de c贸digo, al ser recursivo es sumamente corto

Me tomo algo de tiempo entenderlo as铆 que comparto explicaci贸n a mi manera de enteder.

Comenzamos con 0(a) , 1(b)
luego sumas 0 + 1 = 1(a nuevo)
ahora con el nuevo (a) se lo sumas al (b) antiguo:
1(a nuevo) + 1(b antiguo) = 2(b nuevo)
y obtienes 1(a), 2(b) = 1, 2
asi sucesivamente
1 + 2 = 3
3 +2 = 5
3, 5
3 + 5 = 8
8 + 5 = 13
8, 13
espero que a alguien le sirva

mi soluci贸n de acuerdo a lo que introduzca el usuario el programa va a generar la determinada cantidad de n煤meros que da la sucesi贸n.

Para entender la funci贸n de Fibonacci, me encant贸 esta explicaci贸n de ChatGPT:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) para n >= 2

Aqu铆, F(n) representa el n-茅simo n煤mero en la secuencia de Fibonacci. Por ejemplo, F(0) es el primer n煤mero (0), F(1) es el segundo n煤mero (1), F(2) es el tercer n煤mero (1), F(3) es el cuarto n煤mero (2), y as铆 sucesivamente.

Para calcular un t茅rmino espec铆fico de la serie, necesitas aplicar la f贸rmula F(n) = F(n-1) + F(n-2) sucesivamente, comenzando con los valores iniciales de F(0) y F(1). ****Por ejemplo, para encontrar el sexto n煤mero de Fibonacci (F(5)), ****debes sumar F(4) y F(3):

F(5) = F(4) + F(3)
= (F(3) + F(2)) + (F(2) + F(1))
= ((F(2) + F(1)) + (F(1) + F(0))) + (F(1) + F(0))
= ((1 + 1) + (1 + 0)) + (1 + 0)
= 5

Por lo tanto, el sexto n煤mero de Fibonacci es 5. Puedes continuar este proceso para calcular t茅rminos adicionales de la serie.

Costo entender, pero gracias a los recursos mucho mejor, el siguiente curso debe ser bueno.

Impresi贸n de la secuencia de Fibonacci

def fibonacci(n):
    if n == 0 or n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

n = 0
index = 0

while n < 1:    
    try:
        n = int(input('Escribe el valor de N para el c谩lculo de Fibonacci: '))
    except ValueError:
        n = 0
        
# Se imprime la secuencia
while index < n:
    print(fibonacci(index))
    index += 1

Genial!

javaScript 鉂わ笍

function fibonacci(n) {
if(n == 0 || n == 1){
return 1
};
return fibonacci(n - 1) + fibonacci(n - 2)
};

console.log(fibonacci(5))

N煤meros Fibonacci

En matem谩ticas, la sucesi贸n o serie de Fibonacci hace referencia a la secuencia ordenada de n煤meros descrita por Leonardo de Pisa, matem谩tico italiano del siglo XIII:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,鈥

A cada uno de los elementos de la serie se le conoce con el nombre de n煤mero de Fibonacci.

驴C贸mo se calculan los n煤meros de Fibonacci?

Existen diferentes formas para calcular los n煤meros de Fibonacci:

  1. Partiendo de los n煤meros 0 y 1, los n煤meros de Fibonacci quedan definidos por la funci贸n

  2. Funci贸n generadora: Una funci贸n generadora para una sucesi贸n cualquiera a0, a1, a2,鈥 es la funci贸n f(X) = a0 + a1x + a2x2+鈥, es decir, una serie formal de potencias donde cada coeficiente es un elemento de la sucesi贸n. Los n煤meros de Fibonacci tienen la funci贸n generadora:

  3. F贸rmula expl铆cita: Esta manera de calcular los n煤meros de Fibonacci utiliza la expresi贸n del n煤mero 谩ureo:

a m铆 me ayudo esta explicaci贸n, espero ayude a mas personas de la comunidad.
https://www.youtube.com/watch?v=k6I_TOW6O2o