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;
}
}
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?
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.
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);
}
static int Sum(int value)
{
if (value > 0)
{
return value + Sum(value - 1);
}
else
{
return 0; //Change this.
}
}
Wenn der Wert = 0 ist, wird 1 zurückgegeben. Dann wird es hinzugefügt.
Die "else" -Klausel von Sum sollte 0 zurückgeben.
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.
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.
int summation(int num){
if (num==1)
return 1;
return summation(num-1)+num;
}
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.
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.
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.
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;
}
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
}
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);
}
}
}