Cálculo de números Fibonacci de forma recursiva en Python: Un tutorial completo
Introducción
La secuencia de Fibonacci es una serie de números enteros en la que cada número es la suma de los dos números anteriores. La secuencia comienza con 0 y 1, y los primeros 10 términos son:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
En este tutorial, aprenderemos a calcular los números Fibonacci de forma recursiva en Python.
Recursión
La recursión es un concepto de programación en el que una función se llama a sí misma para resolver un problema. En el caso de la secuencia de Fibonacci, podemos usar la recursión para calcular el n-ésimo término de la secuencia como la suma de los dos términos anteriores.
Implementación en Python
A continuación se muestra un código Python para calcular los números Fibonacci de forma recursiva:
def fibonacci(n):
if n == 0 or n == 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(10))
Este código funciona de la siguiente manera:
- Si el número n es 0 o 1, entonces el término es simplemente n.
- De lo contrario, el término es la suma de los dos términos anteriores.
Ejecutemos el código para ver el resultado:
$ python3 fibonacci.py
34
Explicación
La función fibonacci() toma un número entero n como entrada. Si n es 0 o 1, entonces la función simplemente devuelve n. De lo contrario, la función llama a sí misma dos veces para calcular los dos términos anteriores. La suma de estos dos términos es el valor devuelto por la función.
Análisis de complejidad
El tiempo de ejecución de la función fibonacci() es O(2^n). Esto se debe a que la función se llama a sí misma dos veces en cada paso. El espacio de memoria utilizado por la función es O(n). Esto se debe a que la función almacena los dos términos anteriores en la pila.
Conclusión
En este tutorial, aprendimos a calcular los números Fibonacci de forma recursiva en Python. La recursión es un concepto de programación poderoso que se puede utilizar para resolver una variedad de problemas.
Ejercicios
- Modifique la función
fibonacci()para que imprima los primeros n términos de la secuencia de Fibonacci. - Implemente una versión iterativa de la función
fibonacci(). - Compare el rendimiento de las dos implementaciones.
