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.

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.

Aportes 161

Preguntas 1

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad? Crea una cuenta 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.

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)}')

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

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

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.

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

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

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

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

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

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

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 [email protected] 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)

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)}')

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

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)}')

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

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))

馃槂

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

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>

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

# 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)) 
  

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()

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

Una explicaci贸n gr谩fica respecto al tema:

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')```

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()```

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

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

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.

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)```

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

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)

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```

馃槃 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))

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() 

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))```

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

Amigos hice este humilde programa que imprime la lista de los n primeros n煤meros de fibonnacci 馃槂
Me apoye de dos funciones. fibo(n) validad los casos base y fibo_aux(list,n) calcula de forma recursiva los n煤meros posteriores a la base. Si pueden corregirme o mejorar el programa ser谩 un privilegio 馃槃

def fibo_aux(list, n):
    if len(list) == n:
        return list
    else:
        list.append(sum(list[-2:]))
        return fibo_aux(list, n)


def fibo(n):
    base = [0, 1, 1]
    if n < 1:
        return []
    elif n <= 3:
        return base[:n]
    else:
        return fibo_aux(base, n)


def run():
    cantidad = int(input("Cantidad de n煤meros Fibonnacci: "))
    print(fibo(cantidad))


if __name__ == '__main__':
    run()

Buenas, aqu铆 les comparto mi procedimiento para un Fibonacci m谩s eficiente, usando listas.

def fibonacci(n):
    series = [0, 1]
    for _ in range(2, n+1):
        series.append(sum(series[-2:]))

    return series


def main():
    number = int(input("Type a number: "))
    print(f"The first {number} elements of the fibonacci sequence: ", fibonacci(
        number), sep="\n")


if __name__ == '__main__':
    main()

La funci贸n sum regresa la suma de los elementos de un iterable, y con el -2: nos garantizamos de siempre seleccionar los dos 煤ltimos valores.

Para entender por completo el concepto de la sucesi贸n de Fibonacci pueden ver este video, Derivando es un canal incre铆ble si te gustan las mates

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

Dejo mi explicaci贸n de como funciona este c贸digo, espero sirva:
Intentare explicarlo con mis propias palabras:

  • La funci贸n factorial pone como l铆mite el momento en que retorne 1. Ya que 1!(factorial) es igual a 1.

  • Entonces al ver que n != 1, retorna la multiplicaci贸n de n por el resultado de la funci贸n factorial(n - 1).

  • Como para saber eso necesitamos saber el resultado de esa funci贸n lo que har谩 es a帽adir 20(que por motivos pr谩cticos as铆 llamaremos a n), a un stack, o por decirlo de una forma m谩s clara, a una fila de espera.

  • Lo mismo con factorial(19), que es la resta de n - 1

  • Y as铆 sucesivamente hasta llegar a 1.

  • Cuando llegu茅 a uno, significa que, la fila de espera ya puede avanzar porque ya est谩n todos los valores necesarios.

  • Y multiplicaras en este caso 20, 19, 18, 鈥, 1

  • As铆 completando la funci贸n y retornando el valor que nos ped铆a en la primera vuelta de la funci贸n.

Espero haberlo explicado correctamente! Aqu铆 te dejo un link que muestra como se ejecuta este c贸digo paso a paso si quieres comprobar algo.

Link de Python Tutor

Saludos!

Les comparto mi resumen que me ayud贸 a entender este tema:

Vamos equipo Platzi
馃槈

Fibonacci se entiende mejor as铆:
馃馃馃
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

Otra definici贸n recursiva es el binomio Newtoniano, en este se tiene el caso base de que la sumatoria de i de 0 a n es igual a n/2*(n-1), luego se extrapola a i**2 que es una funci贸n de n a la 3ra potencia --:> n*(n+1)(2n+1)*1/6

Excelente, muchas gracias 馃槂

El aporte de un compa帽ero

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

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

n = int(input('Escribe un entero: '))
print(f'El numero de fibonacci para {n} es {fibonacci(n)}')

encontre este ejemplo espero sirva para entender mejor el concepto de recursividad.

def cuenta_regresiva(numero):
    numero -= 1
    if numero > 0:
        print (numero)
        cuenta_regresiva(numero)
    else:
        print ("Boooooooom!")
    print (f'Fin de la funci贸n {numero}')

numero = int(input('ingrese un numero para cuenta regresiva: '))
cuenta_regresiva(numero)