Una guía sobre la serie de Fibonacci y la recursión en Go

La secuencia de Fibonacci es uno de los problemas más comunes que se resuelven a lo largo de una carrera en software. Su implementación puede ser tan simple o compleja como se quiera.

Una de las soluciones más utilizadas es la recursión, un concepto central en ciencias de la computación. Ya sea que se esté aprendiendo ciencias de la computación, preparando la próxima entrevista o simplemente repasando conceptos antiguos, escribamos juntos una secuencia de Fibonacci usando recursión en Go.

¿Qué es la recursión?

La recursión consiste en dividir un problema en subproblemas más pequeños. A veces se agrega o se quita algo f(n), o hace falta ajustar la solución f(n - 1). En algunos casos, se puede resolver el problema para la mitad del dataset.

En la secuencia de Fibonacci, la función se llama a sí misma con inputs más pequeños. Cada llamada recursiva avanza hacia el caso base.

Enunciado del problema

Dado n, calcular el n-ésimo número de Fibonacci.

La secuencia de Fibonacci es una serie de números en la que cada número es la suma de los dos anteriores, empezando con 0 y 1. La secuencia comienza así: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Desglosándolo:

• Input: un entero donde la serie se detendrá.

• Output: la secuencia desde 0 hasta n.

Ahora que identificamos el input, el output y el enfoque, es momento de implementarlo.

Algoritmo

Primero, dado que la función se llama a sí misma, hace falta evitar bucles infinitos. Para lograrlo, se define un caso base: una condición que le indica a la función cuándo detenerse.

if n <= 1 {
	return n
}

Toda función recursiva consta de dos partes: el caso base (cuándo detenerse) y el caso recursivo (cuándo volver a llamarse). Ya se definió el caso base. Ahora toca declarar el caso recursivo. Para Fibonacci, hace falta llamar a la función dos veces con inputs más pequeños, específicamente n - 1 y n - 2.

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

Es posible que surja la pregunta: “¿Por qué se llama a sí misma dos veces?” Buena pregunta. Cada número es la suma de los dos anteriores.

La función de Fibonacci se define matemáticamente como: F(n) = F(n-1) + F(n-2) para n > 1. 1

Entonces, para calcular F(4), se necesita:

• F(3) (que necesita F(2) y F(1))

• F(2) (que necesita F(1) y F(0))

Fácil, ¿verdad? Y ahí está: ya se resolvió la secuencia de Fibonacci usando recursión. Pero lamento decir que es la peor solución.

Ejemplo visual

¿Por qué aprender algo que es una mala solución? Bueno, porque es el concepto central detrás de soluciones más complejas como dynamic programming o memoization. Si se programa en React, seguramente ya se usó memoization varias veces con los hooks useMemo o useCallback. Por eso hace falta aprender recursión primero.

Un ejemplo lo dejará más claro. Busquemos la secuencia de Fibonacci para el número 4.


Sigamos la recursión paso a paso:

1. F(4) llama a F(3) y F(2)

2. F(3) llama a F(2) y F(1)

   • F(2) llama a F(1) y F(0)

   • F(1) devuelve 1 (caso base)

   • F(0) devuelve 0 (caso base)

   • Entonces F(2) = 1 + 0 = 1

   • F(1) devuelve 1 (caso base)

   • Entonces F(3) = 1 + 1 = 2

3. F(2) llama a F(1) y F(0)

   • F(1) devuelve 1 (caso base)

   • F(0) devuelve 0 (caso base)

   • Entonces F(2) = 1 + 0 = 1

4. Resultado final: F(4) = 2 + 1 = 3

Nótese cómo F(2) se calcula dos veces y F(1) se calcula tres veces. Esta redundancia es la razón por la que la solución recursiva ingenua es ineficiente: tiene una complejidad temporal exponencial de O(2ⁿ). Para valores más grandes de n, los mismos cálculos se repiten miles o incluso millones de veces.

Por eso son necesarias técnicas de optimización como memoization o dynamic programming, que almacenan valores calculados previamente para evitar trabajo redundante.

Reflexiones finales

La recursión conviene usarla cuando hace la solución más clara. Cuando una función llama a otra función, la función que llama queda pausada en un estado parcialmente completo. Imaginemos lo que eso le hace a la memoria.

A pesar de sus desventajas, la recursión es la base de muchos algoritmos importantes, así que vale la pena entender cómo funciona.

Para profundizar o practicar más, se pueden probar otros ejercicios como factorial o las Torres de Hanoi. ¡Feliz coding, nos vemos en la próxima!