Fonctions récursives en Go

La récursivité est une technique de programmation dans laquelle une fonction s'appelle elle-même directement ou indirectement.

Une fonction récursive se compose généralement de deux parties :

  1. Cas de base: Il s'agit de la condition d'arrêt de la récursivité, empêchant la fonction de s'appeler elle-même indéfiniment.
  2. Cas récursif: Ceci est la partie où la fonction s'appelle elle-même, utilisée pour décomposer le problème en sous-problèmes plus petits.

En Go, la récursion est utilisée de manière similaire à d'autres langages, mais certaines fonctionnalités de Go nécessitent une attention particulière.

Le format de la syntaxe est le suivant :

func recursion() {
   recursion() /* la fonction s'appelle elle-même */
}

func main() {
   recursion()
}

Go prend en charge la récursion, mais lors de l'utilisation de la récursion, les développeurs doivent définir une condition de sortie ; sinon, la récursion tombera dans une boucle infinie.

Les fonctions récursives sont très utiles pour résoudre des problèmes mathématiques, comme le calcul des factorielles et la génération de suites de Fibonacci.


factorial

Une factorielle est le produit d'un entier positif, notéen!. Par exemple :

5! = 5 * 4 * 3 * 2 * 1 = 120

L'exemple suivant implémente la factorielle à l'aide de fonctions récursives en Go :

Exemple

package main

import "fmt"

// la fonction récursive calcule la factorielle
func factorial(n int) int {
    // condition de base
    if n == 0 {
        return 1
    }
    // condition récursive
    return n * factorial(n-1)
}

func main() {
    fmt.Println(factorial(5)) // sortie : 120
}

Explication de code

  1. Condition de base: lorsquenLorsqu'il est égal à 0, la fonction renvoie 1, car0!Défini comme 1.
  2. Condition récursive: la fonction renvoienmultiplié parfactorial(n-1)Par conséquent, le problème est progressivement décomposé en sous-problèmes plus petits.

La sortie de l'exécution de l'exemple ci-dessus est :

120

Suite de Fibonacci

L'exemple suivant implémente la suite de Fibonacci à l'aide de fonctions récursives en Go :

Exemple

package main

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 sortie de l'exécution de l'exemple ci-dessus est :

0    1    1    2    3    5    8    13    21    34

racine carrée

L'exemple suivant utilise la récursivité en Go pour implémenter le code permettant de trouver la racine carrée :

Exemple

package main

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 racine carrée de %.2f est %.6f\n", x, result)
}

Dans l'exemple ci-dessus,sqrtRecursiveLa fonction implémente le calcul de la racine carrée à l'aide de la récursivité.

sqrtRecursiveLa fonction accepte quatre paramètres :

  • xReprésente le nombre dont il faut trouver la racine carrée
  • guessReprésente la valeur estimée actuelle de la racine carrée
  • prevGuessReprésente la valeur estimée précédente
  • epsilonReprésente l'exigence de précision (c'est-à-dire la proximité avec la racine carrée)

La condition d'arrêt de la récursivité est que l'estimation actuelle de la racine carrée soit très proche de l'estimation précédente, avec une différence inférieure à la précision epsilon donnée.

Dans la fonction sqrt, nous appelons sqrtRecursive pour calculer la racine carrée, en passant la valeur initiale et l'exigence de précision. Ensuite, dans la fonction main, nous appelons la fonction sqrt pour calculer la racine carrée et afficher le résultat.

La sortie de l'exécution du code ci-dessus est :

25.00 的平方根为 5.000000

Avantages et inconvénients de la récursivité

Avantages

  • Concision: Le code récursif est généralement plus concis et plus facile à comprendre que le code itératif.
  • Décomposition de problème: La récursivité convient naturellement à la résolution de problèmes pouvant être décomposés en sous-problèmes similaires, tels que le parcours d'arbre, les algorithmes diviser pour régner, etc.

Inconvénients

  • Surcoût de performance: Les appels récursifs consomment de l'espace de pile et peuvent provoquer un débordement de pile, en particulier dans la récursivité profonde.
  • Difficulté de débogage: Le code récursif peut être plus difficile à déboguer, en particulier lorsque la profondeur de récursion est grande.

Récursion et itération

La récursion et l'itération sont deux méthodes différentes pour résoudre des problèmes. La récursion résout un problème par une fonction qui s'appelle elle-même, tandis que l'itération utilise des structures de boucle (telles queforboucle) pour exécuter de manière répétée un bloc de code.

Récursion vs Itération

Fonctionnalités Récursion Itération
Concision du code Généralement plus concis Peut être plus verbeux
Performance Peut être plus lent et consommer de l'espace de pile Généralement plus rapide et utilise moins de mémoire
Scénarios applicables Adapté aux problèmes pouvant être décomposés en sous-problèmes Adapté aux problèmes linéaires ou simplement répétitifs

Applications courantes de la récursion

La récursion est largement utilisée dans de nombreux algorithmes et structures de données, par exemple :

  • Parcours d'arbres et de graphes: comme la recherche en profondeur d'abord (DFS).
  • Algorithme diviser pour régner: comme le tri fusion, le tri rapide.
  • Programmation dynamique: comme le calcul de la suite de Fibonacci.

Parcours de répertoires de fichiers

Exemple

import (
    "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(".", "")
}

Lors de l'utilisation de la récursion en Go, une attention particulière doit être portée à la justesse de la condition de base (condition d'arrêt) afin d'éviter une récursion infinie. Pour les scénarios sensibles aux performances ou potentiellement profondément récursifs, il est recommandé d'envisager des implémentations itératives ou d'utiliser des mécanismes spécifiques à Go tels que les canaux/goroutines.

autres extensions