2010-05-06 26 views
7

Eine theoretische Frage hier über den Basis- oder Haltefall in einer rekursiven Methode, welche Standards gibt es?Basisfall in einer rekursiven Methode

Ich meine, ist es normal, Körper in ihm zu haben, nur eine zurückgeben Aussage?

Ist es immer wie folgt aus:

if (input operation value) 
    return sth; 

Haben Sie andere Gedanken darüber haben?

Antwort

1

Der Grundfall ist, die Schleife zu beenden (vermeiden Sie, eine unendliche Rekursion zu werden). Es gibt keinen Standard im Basisfall, jede Eingabe, die einfach genug ist, um genau gelöst zu werden, kann als eine ausgewählt werden.

Zum Beispiel ist dies vollkommen gültig:

int factorial (int n) { 
    if (n <= 5) { 
    // Not just a return statement 
    int x = 1; 
    while (n > 0) { 
     x *= n; 
     -- n; 
    } 
    return x; 
    } else { 
    return n * factorial(n-1); 
    } 
} 
+1

Ich sagte, dass ich eine theoretische Frage stelle, ich meine, wenn ich Rekursion unterrichten will, verwende ich Ihren vorherigen Code nicht, ich weiß, dass es ein gültiger Weg ist, aber es macht Rekursion und das Base Case-Konzept nicht klar genug, was denkst du? – Lisa

7

Das Muster für rekursive Funktionen ist, dass sie in etwa so aussehen:

f(value) 
    if (test value) 
     return value 
    else 
     return f(simplify value) 

Das glaube ich nicht, dass Sie viel mehr sagen können, als das über allgemeine Fälle.

+1

Welche Programmiersprache ist das? – Solace

+4

@Solace Das sieht mehr wie ein Pseudocode aus, keine bestimmte Programmiersprache – Deep

0

Es hängt vollständig von der bestimmten rekursiven Funktion ab. Im Allgemeinen kann es keine leere return;-Anweisung sein - für jede rekursive Funktion, die einen Wert zurückgibt, sollte der Basisfall jedoch auch einen Wert dieses Typs zurückgeben, da func(base) ebenfalls ein vollkommen gültiger Aufruf ist. Beispielsweise würde eine rekursive factorial-Funktion einen 1 als Basiswert zurückgeben.

+0

Eine rekursive Methode muss jedoch keinen Wert zurückgeben. – Ken

+0

Stimmt natürlich. Aber dann könnte ich sagen: Für rekursive Methoden, die 'void' zurückgeben, gibt die Basis auch' void' zurück ...;) – tzaman

1

In einigen Fällen Ihr Basisfall ist

return literal 

In einigen Fällen Ihr Basisfall ist nicht einfach „ein wörtliche zurückkehren“.

Es kann keinen "Standard" geben - das hängt von Ihrer Funktion ab. Die "Syracuse-Funktion" http://en.wikipedia.org/wiki/Collatz_conjecture zum Beispiel hat keinen trivialen Grundfall oder einen trivialen Literalwert.

"Hast du andere Gedanken darüber?" Ist nicht wirklich eine vernünftige Frage.

Die Rekursion muss beendet werden, das ist alles. Eine triviale Tail-Rekursion kann einen "Basisfall" haben, der ein Literal zurückgibt, oder es kann eine Berechnung sein. Eine komplexere Rekursion hat möglicherweise keinen trivialen "Basisfall".

+0

Wenn man versucht, auf dieser Antwort aufzubauen, könnte ein Basisfall in einer rekursiven Funktion auch etwas sein "O (n)" ist wesentlich niedriger als das "O (n)" der tatsächlichen Funktion. Daher wird eine einfachere (weniger komplexe) Operation zurückgegeben. – Deep

Verwandte Themen