In der Welt der Informatik ist Rekursion eine Methode, bei der die Lösung eines Problems von kleineren Instanzen desselben Problems abhängt. Es handelt sich um einen Prozess, bei dem sich eine Funktion selbst als Unterprogramm aufruft. Dadurch kann die Funktion mit weniger Argumenten aufgerufen werden, was die Menge an Zustandsinformationen reduziert, die von der Funktion verwaltet werden müssen, und eine sehr elegante und prägnante Möglichkeit bietet, Lösungen für einige Arten von Problemen auszudrücken. Rekursion wird oft als ein schwierig zu verstehendes Konzept für Anfänger angesehen. Wenn es jedoch richtig verstanden wird, kann es ein äußerst leistungsfähiges Werkzeug im Arsenal eines Programmierers sein. Es kann dazu beitragen, saubereren und prägnanteren Code zu erstellen, und kann häufig zur Lösung komplexer Probleme mit einfachen, eleganten Lösungen verwendet werden.

In dieser Lektion wenden wir die Rekursion auf die Fibonacci-Folge an, eine Reihe von Zahlen, bei der eine Zahl die Addition der letzten beiden Zahlen ist, also 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 usw. Die Folge beginnt bei 0 und daher ist die n-te Zahl die Summe der (n-1)-ten und (n-2)-ten Zahlen.

Rekursive Ansichten in SmartPy

In SmartPy wird Rekursion implementiert, indem einer Funktion ermöglicht wird, sich selbst innerhalb ihrer eigenen Definition aufzurufen. Diese Methode ist äußerst nützlich, wenn Probleme behandelt werden, die in kleinere, identische Teilprobleme zerlegt werden können. Eine rekursive Ansicht in SmartPy ist im Wesentlichen eine Ansicht, die Rekursion verwendet. Eine Ansicht ist eine SmartPy-Funktion, die den Vertragsspeicher nicht ändert, aber daraus lesen kann. Wenn wir von einer rekursiven Ansicht sprechen, meinen wir eine Ansichtsfunktion, die sich während ihrer Ausführung selbst aufruft.

Fibonacci-Folge

Die Fibonacci-Folge ist eine Reihe von Zahlen, wobei jede Zahl die Summe der beiden vorhergehenden Zahlen ist, beginnend bei 0 und 1. Obwohl diese Sequenz einfach ist, bietet sie aufgrund ihrer rekursiven Natur eine hervorragende Grundlage für das Verständnis der Rekursion.

Die Fibonacci-Folge wird durch die Wiederholungsbeziehung definiert:

SCSS 
 F(n) = F(n-1) + F(n-2)

Die Anfangsbedingungen sind F(0) = 0 und F(1) = 1. Das heißt, um die n-te Zahl in der Fibonacci-Folge zu erhalten, addieren wir die (n-1)-te und die (n-2)-te Zahl. Genau diese rekursive Natur macht die Fibonacci-Folge perfekt zum Verständnis der Rekursion geeignet. Nachdem wir nun ein besseres Verständnis der Rekursion und ihrer Anwendung auf die Fibonacci-Folge haben, tauchen wir in den SmartPy-Code ein, der eine rekursive Ansicht zur Berechnung der Fibonacci-Folge implementiert.

Code-Komplettlösung

Der angegebene SmartPy-Code definiert einen Vertrag, FibonacciView, der die Fibonacci-Sequenz mithilfe einer rekursiven Ansicht berechnet. Dies ist ein großartiges Beispiel, um zu verstehen, wie rekursive Funktionen in SmartPy erstellt und verwendet werden.

Python 
 import smartpy as sp 


 @sp.module 
 def main(): 
 class FibonacciView(sp.Contract): 
 """Vertrag mit einer rekursiven Ansicht zur Berechnung der Summe der Fibonacci-Zahlen."""

        @sp.onchain_view() 
 def fibonacci(self, n): 
 """Gib die Summe der Fibonacci-Zahlen bis n zurück.

            Argumente: 
 n (sp.int): Anzahl der zu summierenden Fibonacci-Zahlen.
            Rückgabe: 
 (sp.int): die Summe der Fibonacci-Zahlen 
 """ 
 sp.cast(n, int) 
 wenn n < 2: 
 Rückgabe n 
 sonst: 
 n1 = sp.view("fibonacci", sp.self_address(), n - 1, int).unwrap_some() 
 n2 = sp.view("fibonacci", sp.self_address(), n - 2, int).unwrap_some()
                return n1 + n2 


 if „templates“ not in __name__: 

 @sp.add_test(name="FibonacciView Basic Scenario", is_default=True) 
 def basic_scenario(): 
 sc = sp.test_scenario(main)
        sc.h1("Grundszenario.")
        sc.h2("Entstehung.")
        c1 = main.FibonacciView() 
 sc += c1 
 sc.verify(c1.fibonacci(8) == 21)

Dieser FibonacciView Vertrag verfügt über eine rekursive Ansichtsfunktion, fibonacci, die die n-te Fibonacci-Zahl zurückgibt.

Die Funktion ist mit @sp.onchain_view() versehen, was darauf hinweist, dass es sich um einen schreibgeschützten Vorgang für den Vertragsspeicher handelt. Diese Funktion verwendet eine Ganzzahl n als Argument, die die Position in der Fibonacci-Folge darstellt, die wir abrufen möchten.

Innerhalb der Funktion wandeln wir n aus Sicherheitsgründen zunächst in eine ganze Zahl um. Als nächstes kommt der rekursive Teil der Funktion. Wenn n kleiner als 2 ist, geben wir einfach n zurück, da die ersten beiden Zahlen der Fibonacci-Folge 0 und 1 sind. Wenn n größer oder gleich 2 ist, berechnen wir die n-te Fibonacci-Zahl, indem wir die fibonacci Funktion für n-1 und n-2 rekursiv aufrufen und dann die Ergebnisse addieren. Dies entspricht der Wiederholungsbeziehung, die die Fibonacci-Folge definiert. Die sp.view Aufrufe erstellen diese rekursiven Aufrufe der fibonacci Funktion selbst.

Verwendung einer Schleife für Effizienz 
 Obwohl die Rekursion ein wertvolles Konzept für das Verständnis ist, ist es wichtig zu beachten, dass sie weniger effizient sein und mehr Rechenressourcen erfordern kann, insbesondere wenn es um große Zahlen geht. Um Probleme wie einen Stapelüberlauf zu vermeiden, wäre es effizienter, eine Schleife zur Berechnung der Fibonacci-Folge zu verwenden und die berechneten Fibonacci-Zahlen in einem separaten Vertrag zu speichern.
Hier ist ein allgemeines Beispiel dafür, wie Sie den FibonacciView-Vertrag so ändern können, dass er eine Schleife verwendet: 
 Dieser geänderte Vertrag, FibonacciCalculator, verwendet eine Schleife, um Fibonacci-Zahlen effizient zu berechnen und sie im Speicher des Vertrags zu speichern. Anschließend können Sie den Einstiegspunkt berechne_fibonacci aufrufen, um die n-te Fibonacci-Zahl abzurufen.
Dieser Ansatz ist ressourceneffizienter und für größere Werte von n geeignet.

Python 
 @sp.moduledef main(): 
 class FibonacciCalculator(sp.Contract): 
 """Vertrag zur effizienten Berechnung der Fibonacci-Folge."""def __init__(self): 
 self.init(storage=sp.map(tkey=sp.TInt, tvalue=sp.TInt).set(0, 0).set(1, 1)) 

 @sp.entry_pointdef berechne_fibonacci(self, n): 
 sp.verify(n >= 0, message="n muss nicht negativ sein") 
 storage = self.data 
 für i in range(2, n + 1): 
 next_fib = storage[i - 1] + storage[i - 2] 
 storage = storage.set(i, next_fib) 
 sp.result(storage[n])

Fahren wir mit dem Testabschnitt fort.

In der Testfunktion basic_scenario erstellen wir eine neue Instanz des FibonacciView Vertrags, fügen sie unserem Szenario hinzu und überprüfen dann mit sc.verify , ob die 8. Fibonacci-Zahl 21 ist, was für die Fibonacci-Folge gilt.

Ausführen des Codes in der SmartPy-IDE

So führen Sie den Code aus:

1. Öffnen Sie die SmartPy-IDE.

2. Kopieren Sie den bereitgestellten Code und fügen Sie ihn in den Editor ein.

3. Klicken Sie auf die Schaltfläche „Ausführen“. Sie sollten sehen, dass das Testszenario auf der rechten Seite der IDE ausgeführt wird. Sie sehen die durchgeführten Vorgänge und die überprüften Prüfungen.
   In dieser Lektion wurde viel behandelt. Wir sind von den Grundlagen der Rekursion und ihrer Verwendung in der Programmierung zu rekursiven Ansichten in SmartPy übergegangen und haben diese Konzepte sogar auf die Fibonacci-Folge angewendet. Wir haben auch ein funktionierendes Codebeispiel in SmartPy untersucht und Sie haben gelernt, wie Sie diesen Code in der SmartPy-IDE ausführen und überprüfen.