python logo

Rekursive Programmierung

Python hosting: Host, run, and code Python in the cloud!

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





Leave a Reply: