wake-up-neo.com

Rekursion verwenden, um Zahlen zu summieren

Ich habe gerade das Konzept der Rekursion studiert und dachte, ich würde ein einfaches Beispiel versuchen. Im folgenden Code versuche ich, die Zahlen: 1, 2, 3, 4, 5 zu nehmen und sie mithilfe von Rekursion zusammenzufügen. Ich hatte erwartet, dass das Ergebnis 15 sein wird, aber mein Code gibt 16 zurück. 

Was mache ich falsch?

Code:

    static void Main(string[] args)
    {

        Console.WriteLine(Sum(5));
        Console.Read();
    }


    static int Sum(int value)
    {
        if (value > 0)
        {
          return value + Sum(value - 1);
        }
        else
        {
            return 1;
        }
    }
13
Susan

Sie geben 1 in der else-Klausel zurück. Sie sollten 0 zurückgeben:

else
{
    return 0;
}

Wenn der Wert nicht größer als Null ist, warum sollten Sie zuerst einen Wert zurückgeben?

35
Welbog

Ihr Code wird wie folgt ausgeführt:

Sum --> 5
  Sum --> 4
    Sum --> 3
      Sum --> 2
        Sum --> 1
          Sum --> 0
          1 <---
        2 <---
      4 <---
    7 <---
  11 <---
16 <---

Überprüfen Sie Ihren Basisfall.

17
mweiss

Andere haben den Fehler bereits bemerkt und ich werde auf Rekursion eingehen.

Obwohl C # derzeit keine Tail Call-Optimierung durchführt (obwohl IL über eine spezielle tail-Anweisung verfügt), ist es erwähnenswert, dass die Tail-Rekursion im Allgemeinen eine gute Sache ist. 

Tail-Rekursion ist ein Sonderfall der Rekursion, bei dem die letzte Operation der Funktion, der Tail-Aufruf, ein rekursiver Aufruf ist. Da der letzte Aufruf der rekursive Aufruf ist, ist es nicht erforderlich, den Stack-Frame der aufrufenden Funktion beizubehalten, und der Compiler kann diese Informationen leicht zum Generieren von Maschinenbefehlen verwenden, sodass der Stack überhaupt nicht wächst. Es kann also grundsätzlich eine rekursive Funktion in eine iterative Funktion überführen.

Das Umschreiben Ihres Codes zur Unterstützung der Endrekursion kann wie folgt durchgeführt werden:

static int Sum(int result, int value)
{
    if(value == 0)
        return result;

    return Sum(result + 1, value - 1);
}
13
Anton Gogolev
static int Sum(int value)
{
    if (value > 0)
    {
        return value + Sum(value - 1);
    }
    else
    {
        return 0; //Change this.
    }
}
7
Kirtan

Wenn der Wert = 0 ist, wird 1 zurückgegeben. Dann wird es hinzugefügt.

Die "else" -Klausel von Sum sollte 0 zurückgeben.

5
Mario Marinato

Ich ziehe es immer vor, die abschließenden Fälle vorzustellen, damit sie offensichtlich sind, und ich habe einen gewalttätigen, fast psychopathischen Hass auf "if cond then return a else return b"-Konstrukte. Meine Wahl wäre (klarstellen, dass es bei negativen Zahlen nicht richtig funktioniert):

static unsigned int Sum(unsigned int value) {
    if (value == 0)
        return 0;
    return value + Sum(value - 1);
}

Ich glaube, das ist weitaus lesbarer als ein Morast an Zahnspangen und Kontrollfluss.

4
paxdiablo

Die anderen haben diese Frage bereits beantwortet, aber wenn ich mit Rekursion arbeite, möchte ich gerne überprüfen, ob sie funktioniert, indem sie den Basisfall und einen weiteren Fall verwendet. Ich würde Ihren Fall mit 1 testen, was 2 ergeben würde. Da dies offensichtlich falsch ist, möchten Sie vielleicht nach 0 suchen, was keine Rekursion verwendet. Es sollte also offensichtlich sein, dass der Fehler in der Basisklasse liegt.

Im Allgemeinen ist Rekursion einfacher zu begründen, da Sie die begrenzte Anzahl von Dingen angeben können, die Sie überprüfen müssen, aber dies erfordert zunächst einen Vertrauensvorschuss, da Ihre Intuition falsch sein wird. Testen Sie einfach die Edge-Fälle und vertrauen Sie der Mathematik es wird nie scheitern.

4
tomjen
int summation(int num){

    if (num==1)
        return 1;

    return summation(num-1)+num;
}
4
TAKxic

Ich bin mir ziemlich sicher, dass das Problem darin liegt, dass Ihre Rekursion bei value == 1 beendet werden soll und dass sie derzeit bei value == 0 beendet wird.

1
las3rjock

Ihr abschließender Ausdruck steht zur Debatte. Wenn der Wert == 0 (oder niedriger) ist, sollte er eine 0 anstelle von 1 zurückgeben. Der Effizienz halber (was wir hier zugeben müssen, ist offensichtlich kein Problem, sonst hätte Rekursion für diese Aufgabe nicht verwendet worden). , sollten Sie die Rekursion bei Wert == 1 beenden und ein Literal 1 zurückgeben, um eine unnötige Rekursionsebene zu speichern.

1
Jason Musgrove

Am Ende sieht eine rekursive Sum-Methode folgendermaßen aus:

    // version 3

    public static int Sum(int startRange, int endRange)
    {
        if (endRange > startRange)
        {
            return endRange + Sum(startRange, endRange - 1);

        }

        if (endRange < startRange)
        {
            return startRange + Sum(endRange, startRange - 1);

        }

        return endRange; 

    }

Wenn der Startbereich auf 0 gesetzt ist, erhalten Sie:

    // version 2

    public static int Sum(int range)
    {
        if (range > 0)
        {
            return range + Sum(0, range - 1);

        }

        if (range < 0)
        {
            return Sum(range, -1);

        }

        return range;

    }

... und wenn Sie die Methode nur auf positive Zahlen beschränken möchten, ist kein Zeichen erforderlich:

    // version 1

    public static unsigned int Sum(unsigned int range)
    {
        if (range > 0)
        {
            return range + Sum(0, range - 1);

        }

        return range;

    }

Ich hoffe, dass dies hilft, durch Rekursion mehr Einblick in die Summierung von Zahlenbereichen zu erhalten.

0

Es könnte auch so geschrieben werden:

public static int sum(int n){
    int total;

    if(n==1){
        total =1;

    }else{
        total = sum(n-1)+n;
    }
    return total;
}
0
ekeith

Eigentlich denke ich, dass Sie den Fall sonst nicht prüfen müssen, weil

public static int sum(int number){
    if(number > 0){
       return number + sum(--number);
    }
    return number; // return 0 so that's why you don't need check else condition
}
0
engineer
using System;
using NUnit.Framework;

namespace Recursion
{
  [TestFixture()]
    public class Test
    {
        [Test()]
        public void TestSum ()
        {
            Assert.AreEqual (Sum (new int[] { }), 0);
            Assert.AreEqual (Sum (new int[] { 0 }), 0);
            Assert.AreEqual (Sum (new int[] { 1 }), 1);
            Assert.AreEqual (Sum (new int[] { 1, 2, 3, 4, 5 }), 15);
        }

        public int Sum(int[] head)
        {
            if (head.Length == 0) return 0;

            int[] tail = new int[head.Length - 1];

            for (int i = 1; i < head.Length; i++) 
            {
                tail [i-1] = head [i];
            }

            return head[0] + Sum (tail);
        }
    }
}
0
superlogical