Der Begriff Rekursion kann als der Prozess definiert werden, bei dem etwas anhand seiner selbst definiert wird. In einfachen Worten handelt es sich um einen Prozess, bei dem sich eine Funktion direkt oder indirekt selbst aufruft.
Vorteile der Verwendung von Rekursion
- Eine komplizierte Funktion kann durch Rekursion in kleinere Teilprobleme zerlegt werden.
- Die Sequenzerstellung ist durch Rekursion einfacher als die Verwendung einer verschachtelten Iteration.
- Rekursive Funktionen sorgen dafür, dass der Code einfach und effektiv aussieht.
Nachteile der Verwendung von Rekursion
- Durch rekursive Aufrufe wird viel Speicher und Zeit beansprucht, was die Nutzung teuer macht.
- Rekursive Funktionen sind eine Herausforderung beim Debuggen.
- Die Gründe für die Rekursion können manchmal schwer zu verstehen sein.
Syntax:
def func(): <-- | | (recursive call) | func() ---->
Beispiel 1: Eine Fibonacci-Folge ist die ganzzahlige Folge von 0, 1, 1, 2, 3, 5, 8….
Python3
# Program to print the fibonacci series upto n_terms> # Recursive function> def> recursive_fibonacci(n):> >if> n <>=> 1>:> >return> n> >else>:> >return>(recursive_fibonacci(n>->1>)>+> recursive_fibonacci(n>->2>))> n_terms>=> 10> # check if the number of terms is valid> if> n_terms <>=> 0>:> >print>(>'Invalid input ! Please input a positive value'>)> else>:> >print>(>'Fibonacci series:'>)> for> i>in> range>(n_terms):> >print>(recursive_fibonacci(i))> |
>
>Ausgabe
Fibonacci series: 0 1 1 2 3 5 8 13 21 34>
Beispiel 2: Die Fakultät von 6 wird als 6 bezeichnet! = 1*2*3*4*5*6 = 720.
Python3
# Program to print factorial of a number> # recursively.> # Recursive function> def> recursive_factorial(n):> >if> n>=>=> 1>:> >return> n> >else>:> >return> n>*> recursive_factorial(n>->1>)> # user input> num>=> 6> # check if the input is valid or not> if> num <>0>:> >print>(>'Invalid input ! Please enter a positive number.'>)> elif> num>=>=> 0>:> >print>(>'Factorial of number 0 is 1'>)> else>:> >print>(>'Factorial of number'>, num,>'='>, recursive_factorial(num))> |
>
>Ausgabe
Factorial of number 6 = 720>
Was ist Tail-Rekursion?
Eine einzigartige Art von Rekursion, bei der die letzte Prozedur einer Funktion ein rekursiver Aufruf ist. Die Rekursion kann automatisiert werden, indem die Anforderung im aktuellen Stapelrahmen ausgeführt und die Ausgabe zurückgegeben wird, anstatt einen neuen Stapelrahmen zu generieren. Die Tail-Rekursion kann vom Compiler optimiert werden, wodurch sie besser ist als rekursive Funktionen ohne Tail.
Ist es möglich, ein Programm zu optimieren, indem man eine tail-rekursive Funktion anstelle einer nicht-tail-rekursiven Funktion verwendet?
Wenn wir die unten angegebene Funktion zur Berechnung der Fakultät von n betrachten, können wir beobachten, dass die Funktion zunächst wie eine Schwanzrekursive aussieht, es sich jedoch um eine nicht Schwanzrekursive Funktion handelt. Wenn wir genau hinschauen, können wir erkennen, dass der von Recur_facto(n-1) zurückgegebene Wert in Recur_facto(n) verwendet wird, sodass der Aufruf von Recur_facto(n-1) nicht das letzte ist, was Recur_facto(n) ausführt.
Python3
# Program to calculate factorial of a number> # using a Non-Tail-Recursive function.> # non-tail recursive function> def> Recur_facto(n):> > >if> (n>=>=> 0>):> >return> 1> > >return> n>*> Recur_facto(n>->1>)> > # print the result> print>(Recur_facto(>6>))> |
>
>Ausgabe
720>
Wir können die gegebene Funktion Recur_facto als tail-rekursive Funktion schreiben. Die Idee besteht darin, ein weiteres Argument zu verwenden und im zweiten Argument den Wert der Fakultät unterzubringen. Wenn n 0 erreicht, wird der Endwert der Fakultät der gewünschten Zahl zurückgegeben.
Python3
Gimp Farbe ersetzen
# Program to calculate factorial of a number> # using a Tail-Recursive function.> # A tail recursive function> def> Recur_facto(n, a>=> 1>):> > >if> (n>=>=> 0>):> >return> a> > >return> Recur_facto(n>-> 1>, n>*> a)> > # print the result> print>(Recur_facto(>6>))> |
>
>Ausgabe
720>