Rekursive Programmierung

Einer Funktion ist rekursiv als es sich selbst wieder aufruft. Ein terminal Konditionen ist notwendig, sonst wird es immer dauern.

Python Programming Bootcamp: Go from zero to hero

Rekursion mit ein List
Wir können mit einem einfache Beispiel anfangen: nummern an einen liste hinzufügen Ohne Rekursive Methoden kann es so sein:

#!/usr/bin/env python
 
def sum(list):
    sum = 0
 
    # Add every number in the list.
    for i in range(0, len(list)):
        sum = sum + list[i]
 
    # Return the sum.
    return sum
 
print(sum([5,7,3,8,10]))

Dieser Methoden addiert alle Elementen und gibt die summe.
So können wir das rekursiv machen:

#!/usr/bin/env python
 
def sum(list):
   if len(list) == 1:
        return list[0]
   else:
        return list[0] + sum(list[1:])
 
print(sum([5,7,3,8,10]))

Als die List nur ein Element hat, gibt es direkt der Antwort. Sonst, ruft er die sum() Funktion minus ein Element der liste. Wenn alle anrufen vorbei sind, gibt dieser Funktion der Antwort.

Fakultät mit Rekursion
Der mathematische Definition von Fakultät ist: n! = n * (n-1)!, if n > 1 and f(1) = 1. Zum Beispiel: 3! = 3 x 2 x 1 = 6. Wir können das in Python machen mit einer rekursiven Funktion.

#!/usr/bin/env python
 
def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)
 
print(factorial(3))

Als wir der factorial Funktion anrufen mit n=3, Antwort der Funktion mit n * factorial(n-1). Dieser Prozess wiederholt sich bis n=1. Als n==1 wahr ist, gibt der Funktion der Losung.

Limit

Jeder Funktion Anruf speichert der Computer im Memory. Also, so einer Funktion benutzt mehr Memory. Python wird das Enden nach 1000 anrufen. Wenn Sie diesem Beispiel ausfuhrt:

#!/usr/bin/env python
 
def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)
 
print(factorial(3000))

Bekommst du der Fehler Meldung:

RuntimeError: maximum recursion depth exceeded

Wir können das Losen mit:

#!/usr/bin/env python
import sys
 
sys.setrecursionlimit(5000)
 
def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)
 
print(factorial(3000))

BackNext