¿Me ayudan con la recursividad?

Question

Ya entendí como funciona en el factorial pero cuando se trata de la sucesión de Fibonacci no entiendo cómo funciona

Answer 1

Una definición recursiva simple de una secuencia de Fibonacci sería (usando Python, en otros lenguajes es similar)

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

Aquí, el primer "if" verifica los casos base (fib(1) = fib(2) = 1), y la última línea usa la recursividad para otros casos que definen fib(n) para n>2 en términos de fib(n-1) y fib(n-2)

Por simplicidad, no se realiza ninguna comprobación de argumentos no positivos (o no numéricos). Puede agregar dicho cheque si lo desea

Esta implementación simple sería lenta para n grandes, ya que para cada n> 2 iniciaría dos funciones nuevas, que a su vez iniciarían dos nuevas, etc.

Para ser más rápido, hagamos que nuestra función devuelva dos valores: fib(n) y fib(n + 1)

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

Aquí solo necesitamos un caso base, y el caso recursivo está haciendo solo una llamada a fib2, ya que esta llamada nos da tanto fib(n - 1) como fib(n)

Answer 2

Puede hacerlo aún más rápido (logarítmico en n) usando operaciones monoide, por ejemplo, multiplicaciones de matrices, pero espero que estos dos ejemplos sean suficientes para explicar cómo funciona la recursividad en este caso

Answer 3

Gracias ya entendí como funciona la recursividad en este caso