Frage Rekursion zur Summenbildung verwenden


Ich habe gerade das Konzept der Rekursion studiert und ich dachte, dass ich ein einfaches Beispiel versuchen würde. Im folgenden Code versuche ich, die Zahlen zu nehmen: 1, 2, 3, 4, 5, und addiere sie durch Rekursion. Ich habe erwartet, dass das Ergebnis 15 ist, 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;
        }
    }

12
2018-04-24 13:40


Ursprung


Antworten:


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

else
{
    return 0;
}

Wenn der Wert nicht größer als Null ist, warum würden Sie dann einen zurückgeben?


35
2018-04-24 13:43



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üfe deinen Basisfall.


17
2018-04-24 13:44



Andere bemerkten bereits den Fehler, und ich werde auf die Rekursion eingehen.

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

Schwanz Rekursion ist ein Sonderfall der Rekursion, bei der die letzte Operation der Funktion, der Tail-Aufruf, ein rekursiver Aufruf ist. Da der letzte Aufruf der rekursive Aufruf ist, besteht keine Notwendigkeit, den Stapelrahmen der aufrufenden Funktion beizubehalten, und der Compiler kann diese Information leicht verwenden, um Maschinenbefehl zu erzeugen, so dass der Stapel überhaupt nicht wächst. So kann es die rekursive Funktion im Grunde zu einer iterativen Funktion machen.

Das Umschreiben Ihres Codes zur Unterstützung der Tail-Rekursion 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
2018-04-24 13:50



static int Sum(int value)
{
    if (value > 0)
    {
        return value + Sum(value - 1);
    }
    else
    {
        return 0; //Change this.
    }
}

6
2018-04-24 13:44



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

Sums "else" -Klausel sollte 0 zurückgeben.


5
2018-04-24 13:44



Ich ziehe es immer vor, die abschließenden Fälle nach vorne zu legen, damit sie offensichtlich sind, und ich habe einen heftigen, fast psychopathischen Hass auf "if cond then return a else return b" konstruiert. Meine Wahl wäre (klarzustellen, dass es für negative 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 viel lesbarer als ein Morast aus Zahnspangen und Kontrollfluss.


4
2018-04-24 13:50



Die anderen haben diese Frage bereits beantwortet, aber wenn ich mit der Rekursion arbeite, ist eines der Dinge, die ich tun möchte, um zu überprüfen, ob es funktioniert, die Verwendung des Basisfalls und eines zusätzlichen Falls. In Ihrem Fall würde ich es mit 1 testen, was 2 ergeben würde. Da dies offensichtlich falsch ist, möchten Sie vielleicht nach 0 suchen, das keine Rekursion verwenden wird, und daher sollte es offensichtlich sein, dass der Fehler in der Basisklasse liegt.

Im Allgemeinen ist Rekursion einfacher zu verstehen, da Sie die begrenzte Anzahl von Dingen auflisten können, die Sie überprüfen müssen, aber es erfordert zunächst einen Vertrauensvorschuss, da Ihre Intuition falsch ist. Testen Sie einfach die Randfälle und vertraue der Mathematik es wird noch nie Scheitern.


4
2018-04-24 13:57



int summation(int num){

    if (num==1)
        return 1;

    return summation(num-1)+num;
}

3
2017-07-22 12:05