0

¿Me ayudan con la recursividad?

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

16th Nov 2020, 5:08 AM
Andy Eliu González Pérez
Andy Eliu González Pérez - avatar
3 odpowiedzi
+ 2
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)
16th Nov 2020, 6:16 AM
Volodymyr Chelnokov
Volodymyr Chelnokov - avatar
0
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
16th Nov 2020, 6:16 AM
Volodymyr Chelnokov
Volodymyr Chelnokov - avatar
0
Gracias ya entendí como funciona la recursividad en este caso
16th Nov 2020, 5:50 PM
Andy Eliu González Pérez
Andy Eliu González Pérez - avatar