C # - Création d'une fonction récursive pour calculer la somme d'une liste. Est-il possible d'utiliser uniquement la liste comme le seul paramètre?

Ce sont quelques façons d'obtenir la somme des entiers dans une liste.

Vous n'avez pas besoin d'une méthode récursive, il passe plus de ressources système quand ce n'est pas nécessaire. P>

class Program
{
    static void Main(string[] args)
    {
        List<int> numbers = new List<int>() { 1, 2, 3, 4, 5 };
        int sum1 = numbers.Sum();
        int sum2 = GetSum2(numbers);
        int sum3 = GetSum3(numbers);
        int sum4 = GetSum4(numbers);
    }

    private static int GetSum2(List<int> numbers)
    {
        int total = 0;
        foreach (int number in numbers)
        {
            total += number;
        }
        return total;
    }

    private static int GetSum3(List<int> numbers)
    {
        int total = 0;
        for (int i = 0; i < numbers.Count; i++)
        {
            total += numbers[i];
        }
        return total;
    }

    private static int GetSum4(List<int> numbers)
    {
        int total = 0;
        numbers.ForEach((number) =>
        {
            total += number;
        });
        return total;
    }
}

Ainsi, dans ma tentative de commencer à apprendre C # Un défi, j'ai rencontré est de créer une fonction récursive qui calculera la somme d'une liste. Je me demande s'il est possible de faire cela en utilisant une liste comme seul argument de la fonction? Ou devrais-je appliquer une taille d'index aussi pour travailler via la liste?

C'est un excellent exercice pour un débutant. Cependant, vous ne le feriez jamais avec une liste dans un programme réaliste. Tout d'abord, parce que vous appeliez simplement .sum () dessus. Mais c'est un flexible; Quelqu'un a dû écrire somme , et cette personne pourrait être toi.

La raison pour laquelle vous ne feriez jamais que cette liste est de la liste n'est pas une structure de données récursif. Comme vous le note, chaque fois que vous recurrez, il doit y avoir quelque chose de différent . S'il n'y a pas quelque chose de différent, vous avez une récursion sans bornes!

Cela signifie que vous devez modifier l'un des arguments, que ce soit en la mutateur, s'il s'agit d'un type de référence ou de transmettre un argument différent. ni n'est correct dans ce cas où l'argument est une liste .

Pour une liste, vous ne voulez jamais muter la liste, en supprimant les articles, par exemple. Vous ne possédez pas cette liste . L'appelant possède la liste et il est impoli de la muter sur eux. Lorsque j'appelle votre méthode pour résumer une liste, je ne veux pas que la liste soit vidée; Je voudrais peut-être l'utiliser pour autre chose.

Et pour une liste, vous ne voulez jamais transmettre une liste différente dans une récursion car construire la nouvelle liste de l'ancienne liste est très coûteux . .

(Il y a aussi la question de la récursion profonde; vraisemblablement, nous souhaitons résumer des listes de plus de mille chiffres, mais cela mangera tout l'espace de pile si vous allez avec une solution récursive; c # n'est pas une queue garantie -Récours similaire comme F # est. Toutefois, à des fins d'apprentissage, ignorons ce problème et supposons que nous ne traitons que de petites listes.)

Comme les deux techniques permettant d'éviter les récursions sans bornes sont inapplicables, vous ne devez pas écrire des algorithmes récursifs sur list (ou, comme vous le souhaitez, vous devez transmettre un paramètre auxiliaire tel qu'un index , et c'est la chose que vous changez). Mais votre exercice est toujours valide; Nous devons simplement en faire un meilleur exercice en demandant «Que devrions-nous devoir changer pour faire une liste susceptible de récursion?»

Nous devons changer deux choses: (1) rendre la liste immuable, et (2) en faire une structure de données définie de manière récursive. S'il est immuable, vous ne pouvez pas modifier les données de l'appelant par accident; C'est inconnu. Et s'il s'agit d'une structure de données définie de manière récursive, il existe un moyen naturel de réursion sur celui-ci qui est bon marché.

Voici votre nouvel exercice:

• Un immutableliste est (1) vide ou (2) un seul entier, appelé "Head" et une liste immuable, appelée "queue". Les mettre en œuvre à la manière de choisir. (Classe de base abstraite, interface mise en œuvre par plusieurs classes, classe unique qui fait le tout, tout ce que vous pensez est préférable. Portez une attention particulière aux constructeurs.)
• immutablelist a trois propriétés en lecture seule publiques: bool iSeMTY , int Head et immutableliste queue . Les mettre en œuvre.
• Nous pouvons maintenant définir int Somme (immutablelist) en tant que méthode récursive: le boîtier de base est la somme d'une liste vide est zéro; Le cas inductif est la somme d'une liste non vide est la tête plus la somme de la queue. Mettre en œuvre; pouvez-vous le faire comme une seule ligne de code?

  Vous en apprendrez beaucoup plus sur C # et la programmation dans un style fonctionnel avec cet exercice. Utilisez des algorithmes itératifs sur Liste , toujours; C'est ce qu'il a été conçu pour. Utilisez la récursion sur les structures de données conçues pour la récursivité.

  Exercices de bonus:

  • écriture somme comme méthode d'extension, de sorte que vous pouvez appeler myimmutablelist.sum () .
  • la somme est un cas particulier d'une opération appelée agrégat . Il renvoie un entier et prend trois paramètres: une liste immuable, un entier appelé l'accumulateur et un Func . Si la liste est vide, le résultat est l'accumulateur. Sinon, le résultat est la récursion sur la queue et appelant la fonction sur la tête et l'accumulateur. Écrivez un agrégat récursif ; Si vous avez terminé correctement, alors int Somme (immutablelist) => Agrégat (éléments, 0, (ACC, élément) => ACC + Item); devrait être une implémentation correcte de Somme .
  • genericiser immutablelist à immutablelist ; genericiser agrégat à agrégat où t est le type d'élément de liste et r est le type d'accumulateur .