Quelle est la différence entre résoudre une même tâche par récursion et par boucle ?

Différence dans l’approche et le mécanisme d’exécution.

Récursion :

• La fonction s’appelle elle-même pour résoudre une sous-tâche.
• Utilise une pile d’appels pour stocker l’état.
• Approche plus déclarative, peut être plus facile à comprendre pour certaines tâches (par exemple, parcours d’arbre).
• Peut entraîner un dépassement de pile en cas de profondeur de récursion trop grande.
• Généralement moins efficace en mémoire et en performance en raison des coûts supplémentaires liés aux appels de fonctions et à la gestion de la pile.

Boucle :

• Utilise l’itération avec des constructions for, while, do-while.
• N’utilise pas de pile d’appels pour gérer les itérations (sauf mécanismes internes du compilateur/environnement).
• Approche plus impérative, décrit explicitement les étapes d’exécution.
• N’est pas sujette au risque de dépassement de pile lors d’itérations longues.
• En général, plus efficace en mémoire et en performance.

Exemple : Calcul du factoriel.

Approche récursive :

// Calcul récursif du factoriel
public int FactorialRecursive(int n)
{
    if (n == 0)
    {
        return 1; // Cas de base
    }
    else
    {
        return n * FactorialRecursive(n - 1); // Étape récursive
    }
}

Approche itérative :

// Calcul itératif du factoriel
public int FactorialIterative(int n)
{
    int result = 1;
    for (int i = 2; i <= n; i++)
    {
        result *= i;
    }
    return result;
}

Dans cet exemple, la mise en œuvre itérative est plus préférée en termes de performance et pour éviter le dépassement de pile pour de grandes valeurs de n. Cependant, pour des tâches décrites naturellement de manière récursive (par exemple, parcours de graphes/arborescences), la solution récursive peut être plus intuitive. Toute fonction récursive peut être transformée en une version itérative en utilisant une pile explicite.