Funciones recursivas en Go
La recursión es una técnica de programación en la que una función se llama a sí misma directa o indirectamente.
Una función recursiva generalmente consta de dos partes:
- Caso base (Base Case): esta es la condición de terminación de la recursión, que evita que la función se llame a sí misma infinitamente.
- Caso recursivo (Recursive Case): es la parte donde la función se llama a sí misma, utilizada para descomponer el problema en subproblemas más pequeños.
En Go, el uso de la recursión es similar al de otros lenguajes, pero hay que tener en cuenta algunas características de Go.
El formato de sintaxis es el siguiente:
recursion() /* La función se llama a sí misma */
}
func main() {
recursion()
}
Go admite la recursión, pero al usarla, el desarrollador debe establecer una condición de salida; de lo contrario, la recursión caerá en un bucle infinito.
Las funciones recursivas son muy útiles para resolver problemas matemáticos, como calcular factoriales, generar la sucesión de Fibonacci, etc.
Factorial
El factorial es el producto de un entero positivo, representado comon!. Por ejemplo:
5! = 5 * 4 * 3 * 2 * 1 = 120
El siguiente ejemplo calcula el factorial mediante una función recursiva en Go:
Ejemplo
import "fmt"
// Función recursiva para calcular el factorial
func factorial(n int) int {
// Caso base
if n == 0 {
return 1
}
// Caso recursivo
return n * factorial(n-1)
}
func main() {
fmt.Println(factorial(5)) // Salida: 120
}
Explicación del código
- Caso base: cuando
nes igual a 0, la función devuelve 1, porque0!se define como 1. - Caso recursivo: la función devuelve
nmultiplicado porfactorial(n-1)el resultado, descomponiendo gradualmente el problema en subproblemas más pequeños.
La salida de la ejecución del ejemplo anterior es:
120
Sucesión de Fibonacci
El siguiente ejemplo implementa la sucesión de Fibonacci mediante una función recursiva en Go:
Ejemplo
import "fmt"
func fibonacci(n int) int {
if n < 2 {
return n
}
return fibonacci(n-2) + fibonacci(n-1)
}
func main() {
var i int
for i = 0; i < 10; i++ {
fmt.Printf("%d\t", fibonacci(i))
}
}
La salida de la ejecución del ejemplo anterior es:
0 1 1 2 3 5 8 13 21 34
Calcular la raíz cuadrada
El siguiente ejemplo muestra el código en Go para calcular la raíz cuadrada mediante el método recursivo:
Ejemplo
import (
"fmt"
)
func sqrtRecursive(x, guess, prevGuess, epsilon float64) float64 {
if diff := guess*guess - x; diff < epsilon && -diff < epsilon {
return guess
}
newGuess := (guess + x/guess) / 2
if newGuess == prevGuess {
return guess
}
return sqrtRecursive(x, newGuess, guess, epsilon)
}
func sqrt(x float64) float64 {
return sqrtRecursive(x, 1.0, 0.0, 1e-9)
}
func main() {
x := 25.0
result := sqrt(x)
fmt.Printf("La raíz cuadrada de %.2f es %.6f"\n", x, result)
}
En el ejemplo anterior,sqrtRecursivela función utiliza la recursión para calcular la raíz cuadrada.
sqrtRecursiveLa función acepta cuatro parámetros:
- xrepresenta el número del que se desea calcular la raíz cuadrada
- guessrepresenta el valor actual estimado de la raíz cuadrada
- prevGuessrepresenta el valor estimado anterior
- epsilonrepresenta el requisito de precisión (es decir, qué tan cerca de la raíz cuadrada)
La condición de terminación de la recursión es que la raíz cuadrada estimada actual esté muy cerca de la estimación anterior, con una diferencia menor que la precisión epsilon dada.
En la función sqrt, llamamos a sqrtRecursive para calcular la raíz cuadrada, pasando el valor inicial y el requisito de precisión; luego, en la función main, llamamos a la función sqrt para resolver la raíz cuadrada e imprimimos el resultado.
La salida de la ejecución del código anterior es:
25.00 的平方根为 5.000000
Ventajas y desventajas de la recursión
Ventajas
- Simplicidad: el código recursivo suele ser más conciso que el iterativo y más fácil de entender.
- Descomposición de problemas: la recursión es naturalmente adecuada para resolver problemas que pueden descomponerse en subproblemas similares, como el recorrido de árboles, algoritmos de divide y vencerás, etc.
Desventajas
- Costo de rendimiento: las llamadas recursivas ocupan espacio en la pila, lo que puede provocar desbordamiento de pila, especialmente en recursión profunda.
- Dificultad de depuración: el código recursivo puede ser difícil de depurar, especialmente cuando la profundidad de recursión es grande.
Recursión e iteración
La recursión y la iteración son dos métodos diferentes para resolver problemas. La recursión resuelve problemas haciendo que una función se llame a sí misma, mientras que la iteración repite un bloque de código mediante estructuras de bucle (comoforbucle) para ejecutar repetidamente un bloque de código.
Recursión vs iteración
| Característica | Recursión | Iteración |
|---|---|---|
| Simplicidad del código | Generalmente más conciso | Puede ser más extenso |
| Rendimiento | Puede ser más lento, ocupa espacio en la pila | Generalmente más rápido, ocupa menos memoria |
| Escenarios de aplicación | Adecuado para problemas que se descomponen en subproblemas | Adecuado para problemas lineales o de repetición simple |
Aplicaciones comunes de la recursión
La recursión se usa ampliamente en muchos algoritmos y estructuras de datos, por ejemplo:
- Recorrido de árboles y grafos: como la búsqueda en profundidad (DFS).
- Algoritmos de divide y vencerás: como la ordenación por mezcla (merge sort), la ordenación rápida (quick sort).
- Programación dinámica: como el cálculo de la sucesión de Fibonacci.
Recorrido de directorios de archivos
Ejemplo
"fmt"
"os"
"path/filepath"
)
func walkDir(dir string, indent string) {
entries, err := os.ReadDir(dir)
if err != nil {
return
}
for _, entry := range entries {
fmt.Println(indent + entry.Name())
if entry.IsDir() {
walkDir(filepath.Join(dir, entry.Name()), indent+" ")
}
}
}
func main() {
walkDir(".", "")
}
Al usar recursión en Go, se debe prestar especial atención a la corrección de la condición base (condición de terminación) para evitar una recursión infinita. Para escenarios sensibles al rendimiento o con posible recursión profunda, se recomienda considerar una implementación iterativa o utilizar mecanismos específicos de Go como channel/goroutine.
Otras extensiones