Récursivité

De Banane Atomic
Aller à la navigationAller à la recherche

Généralités

L’utilisation massive de la call stack peut amoindrir les performances.

Factorielle

Csharp.svg
private static int Factorielle(int i)
{
    if (i == 1)
    {
        return 1;
    }
    else
    {
        return i * Factorielle(i - 1);
    }
}
i = 3
return 3 * Factorielle(2)
return 2 * Factorielle(1)
return 1

Invertion d'une chaine de caractères

Csharp.svg
private string Reverse(string input)
{
    if (input.Length == 1)
    {
        return input;
    }
    
    // version 1: on met le premier caractère à la fin
    return Reverse(input.Substring(1)) + input[0];
    // version 2: on met le dernier caractère en premier
    return input.Last() + Reverse(input.Substring(0, input.Length - 1));
}
v1
input = "abc"
return Reverse("bc") + "a"
return Reverse("c") + "b"
return "c"

v2
input = "abc"
return "c" + Reverse("ab")
return "b" + Reverse("a")
return "a"

Calcul arithmétique

Csharp.svg
private Dictionary<char, Func<decimal, decimal, decimal>> operations =
    new Dictionary<char, Func<decimal, decimal, decimal>>
    {
        ['+'] = (current, next) => current + next,
        ['-'] = (current, next) => current - next,
        ['/'] = (current, next) => current / next,
        ['*'] = (current, next) => current * next
    };

public decimal Evaluate(string expression)
{
    foreach (var operation in operations)
    {
        if (expression.Contains(operation.Key))
        {
            var parts = expression.Split(operation.Key);

            return parts.Skip(1).Aggregate(
                Evaluate(parts[0]),
                (current, next) => operation.Value(current, Evaluate(next)));
            // équivalent à
            var total = Evaluate(parts[0]);
            for (int i = 1; i < parts.Length; i++)
            {
                total = operation.Value(total, Evaluate(parts[i]));
            }
            return total;
        }
    }

    decimal.TryParse(expression, out decimal value);
    return value;
}
expression = "1 + 2 * 3"
split + : ["1", "2 * 3"]
Evaluate("1") → return 1
Evaluate("2 * 3")
split * : ["2", "3"]
Evaluate("2") → return 2
Evaluate("3") → return 3
operation * → 2 * 3 = 6
operation + → 1 + 6 = 7

expression = "2 * 3 + 1"
split + : ["2 * 3", "1"]
Evaluate("2 * 3")
split * : ["2", "3"]
Evaluate("2") → return 2
Evaluate("3") → return 3
operation * → 2 * 3 = 6
Evaluate("1") → return 1
operation + → 6 + 1 = 7