Funciones recursivas en Go

La recursividad es la habilidad de una función de llamarse a sí misma. Esta característica permite reducir y simplificar operaciones complejas, tales como una navegación jerárquica en un árbol o el cálculo de operaciones matemáticas como el factorial.

package main

import "fmt"

func main() {
   // factorial(5) = 5 * 4 * 3 * 2 * 1 = 120
   fmt.Println("Factorial de 5: ", factorial(5))
}

// Funcion que calcula un factorial
func factorial(n int) int {
   if n == 0 {
      return 1
   }

   return n * factorial(n-1)
}

Hay que tener en cuenta que cada vez que se llama a sí misma se crea un nuevo nivel de ejecución, en el que, hasta que el nivel más profundo no termina, no se irá resolviendo el retorno de las llamadas hacia atrás.

También hay que tener en cuenta que hay que controlar el nivel de profundidad de llamadas, para evitar un colapso en la memoria, al entrar en una recursividad infinita.

En el ejemplo del factorial, se va llamando a sí misma con el cálculo del factorial del número decrementado, hasta llegar a 1, momento en el que deja de llamarse a sí misma, y, por tanto, en ese momento termina la recursividad (y la profundidad de la misma) y comienza el retorno hacia atrás del resultado, disminuyendo nuevamente la profundidad de las llamadas hasta el primer nivel.

El siguiente ejemplo permite calcular la secuencia Fibonacci. Para limitar la recursividad, el factor de la secuencia debe ser mayor de 1.

package main

import "fmt"

func main() {
   // fibonacci(7) = 0 1 2 3 5 8 13
   fmt.Println("fibonacci(7): ", fibonacci(7))
}


// Funcion que calcula la secuencia fibonacci
func fibonacci(i int) int {
   if i <= 1 {
      return i
   }

   return fibonacci(i-1) + fibonacci(i-2)
}

Enlaces de interés

• Go by Example - recursion:https://gobyexample.com/recursion