Eine rekursive Funktion ist eine Funktion, die sich innerhalb der Funktion aufruft. Der folgende Code ist beispielsweise eine rekursive Funktion.
def hello
puts 'hello!'
hello
end
hello
In der Funktion mit dem Namen "Hallo" wird die Funktion "Hallo" nach der Ausgabe der Zeichenfolge "Hallo!" Erneut aufgerufen. Übrigens, wenn ich den obigen Code ausführe, wird die Zeichenfolge "Hallo!" Die ganze Zeit ausgegeben. (Wenn es rubinrot ist, wird es mit "Systemstapelfehler" zwangsweise beendet.)
Wenn Sie nur eine rekursive Funktion erstellen, erreicht der obige Code Ihr Ziel. Da jedoch eine rekursive Funktion, die eine Zeichenfolge ausgibt, nicht interessant ist, nehmen wir die "Berechnung des Maßstabs" als Grundproblem für die Implementierung einer rekursiven Funktion. Ich habe den Code geschrieben, um die Potenz von n zu berechnen. Lassen Sie es uns zunächst implementieren, ohne eine rekursive Funktion zu verwenden.
res = 1
while n > 0
res *= n
n -= 1
end
puts res
Ist es so Ruby hat auch eine praktische Methode, die als "times" -Methode bezeichnet wird. Wenn Sie diese verwenden, ist dies wie folgt.
res = 1
n.times do |i|
res *= (i + 1)
end
puts res
In beiden Fällen kann die Leistung berechnet werden, indem eine natürliche Zahl an "n" übergeben wird. Lassen Sie uns dies mit einer rekursiven Funktion implementieren. Der Code sieht folgendermaßen aus:
def factorial(n)
if n == 0
1
else
n * factorial(n - 1)
end
end
Wenn Sie der Funktion "Fakultät" eine natürliche Zahl übergeben, gibt das Programm das Ergebnis der Multiplikation zurück. Wenn Sie nicht damit vertraut sind, ist es schwierig zu verstehen, um welche Art von Verarbeitungsablauf es sich handelt. Verfolgen wir die Verarbeitung am Beispiel von "n = 3".
Wenn Sie "n = 3" als Argument an "Fraktion" übergeben, wertet der "if-else" -Block "n" aus und verzweigt sich. Da "n = 3" ist, wird die Verarbeitung von "else" ausgeführt und "3 * fraktion (2)" zurückgegeben.
Da wir jedoch die Funktion "Fraktion" für den Rückgabewert aufrufen, wird der Prozess auch hier ausgeführt und das Ergebnis zurückgegeben. fraktion (2) gibt 2 * fraktion (1) zurück.
In ähnlicher Weise gibt "Fraktion (1)" 1 * Fraktion (0) "zurück.
Hier gibt factional (0) abhängig von der Bedingung des if-else-Blocks 1 zurück.
Infolgedessen gibt "Fraktion (3)" 3 * 2 * 1 * 1 "zurück und Sie erhalten die gewünschte Antwort" 3! = 6 ".
Beim Erstellen einer rekursiven Funktion ist ** eine Bedingung zum Beenden des Prozesses ** erforderlich. Eine solche Bedingung wird als ** Basisfall ** bezeichnet. Wenn der Basisfall nicht festgelegt ist, endet die rekursive Funktion in einer Endlosschleife. Ein Basisfall ist wichtig, um Endlosschleifen zu vermeiden. In diesem Multiplikationsberechnungscode ist der Fall von "n = 0" der Basisfall. Es ist auch wichtig, einen Prozess zu erstellen, mit dem Sie den ** Basisfall erreichen können. ** Selbst wenn Sie einen Basisfall vorbereiten, wird der Prozess nicht beendet, wenn Sie den Basisfall nicht erreichen. Der folgende Code führt beispielsweise zu einer Endlosschleife.
def factorial(n)
if n == 0.5
1
else
n * factorial(n - 1)
end
end
Die Bedingung von "if" ist ein Dezimalpunkt. Da n eine natürliche Zahl ist, gibt es keinen Fall, in dem n ein Bruch ist. In einem solchen Beispiel kann der Basisfall nicht erreicht werden.
Die Möglichkeit, eine Schleifenverarbeitung mit rekursiven Funktionen zu schreiben, erweitert den Programmierbereich. Außerdem ist die Idee rekursiver Funktionen wichtig (anscheinend noch zu studieren), wenn Algorithmen wie die Suche mit Tiefenpriorität implementiert werden. In einem einfachen Beispiel wie dieser Multiplikationsberechnung scheint es einfacher zu verstehen, ob sie in einer normalen Schleife implementiert ist, aber wenn Sie einen Algorithmus wie die Suche nach Tiefenprioritäten implementieren, ist es einfach, eine rekursive Funktion zu verwenden. Ich denke, es kann mit einfachem Code implementiert werden.
qiita: Welche Art von Welt wird sich erweitern, wenn Sie rekursive Funktionen lernen
Recommended Posts