wake-up-neo.com

Wie kann ich eine rekursive Funktion in Python erstellen?

Wie kann ich eine rekursive Funktion in Python erstellen?

41
sddaf ads

Ich frage mich, ob Sie "rekursiv" gemeint haben. Hier ist ein einfaches Beispiel einer rekursiven Funktion zur Berechnung der Fakultätsfunktion :

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

Die zwei Schlüsselelemente eines rekursiven Algorithmus sind:

  • Die Kündigungsbedingung: n == 0
  • Der Reduktionsschritt, bei dem sich die Funktion jedes Mal mit einer kleineren Nummer aufruft: factorial(n - 1)
81
Greg Hewgill

Rekursion in Python funktioniert genauso wie Rekursion in einer anderen Sprache, wobei das rekursive Konstrukt in sich selbst definiert ist:

Eine rekursive Klasse kann beispielsweise ein Binärbaum (oder ein beliebiger Baum) sein:

class tree():
    def __init__(self):
        '''Initialise the tree'''
        self.Data = None
        self.Count = 0
        self.LeftSubtree = None
        self.RightSubtree = None

    def Insert(self, data):
        '''Add an item of data to the tree'''
        if self.Data == None:
            self.Data = data
            self.Count += 1
        Elif data < self.Data:
            if self.LeftSubtree == None:
                # tree is a recurive class definition
                self.LeftSubtree = tree()
            # Insert is a recursive function
            self.LeftSubtree.Insert(data)
        Elif data == self.Data:
            self.Count += 1
        Elif data > self.Data:
            if self.RightSubtree == None:
                self.RightSubtree = tree()
            self.RightSubtree.Insert(data)

if __== '__main__':
    T = tree()
    # The root node
    T.Insert('b')
    # Will be put into the left subtree
    T.Insert('a')
    # Will be put into the right subtree
    T.Insert('c')

Wie bereits erwähnt, muss eine rekursive Struktur eine Abbruchbedingung haben. In dieser Klasse ist dies nicht so offensichtlich, da es nur dann wiederkehrt, wenn neue Elemente hinzugefügt werden, und dies nur ein einziges Mal zusätzlich.

Erwähnenswert ist auch, dass python standardmäßig eine Begrenzung der Rekursionstiefe hat, um zu vermeiden, dass der gesamte Arbeitsspeicher des Computers belegt wird. Auf meinem Computer ist dies 1000. Ich weiß nicht, ob sich dies ändert je nach Hardware, etc. So sehen Sie Ihre:

import sys
sys.getrecursionlimit()

und um es einzustellen:

import sys #(if you haven't already)
sys.setrecursionlimit()

bearbeiten: Ich kann nicht garantieren, dass mein Binärbaum das effizienteste Design aller Zeiten ist. Wenn jemand es verbessern kann, würde ich mich freuen zu hören, wie

11

Nehmen wir an, Sie möchten bauen: u (n + 1) = f (u (n)) mit u (0) = u0

Eine Lösung besteht darin, eine einfache rekursive Funktion zu definieren:

u0 = ...

def f(x):
  ...

def u(n):
  if n==0: return u0
  return f(u(n-1))

Wenn Sie hohe Werte für u berechnen möchten, tritt leider ein Stapelüberlauffehler auf.

Eine andere Lösung ist eine einfache Schleife:

def u(n):
  ux = u0
  for i in xrange(n):
    ux=f(ux)
  return ux

Wenn Sie jedoch mehrere Werte von u für verschiedene Werte von n möchten, ist dies nicht optimal. Sie könnten alle Werte in einem Array zwischenspeichern, aber möglicherweise tritt ein Speicherfehler auf. Möglicherweise möchten Sie stattdessen Generatoren verwenden:

def u(n):
  ux = u0
  for i in xrange(n):
    ux=f(ux)
  yield ux

for val in u(1000):
  print val

Es gibt viele andere Optionen, aber ich denke, das sind die wichtigsten.

5
MiniQuark

Beispiel für eine rekursive Funktion:

def recursive(string, num):
    print "#%s - %s" % (string, num)
    recursive(string, num+1)

Führen Sie es mit:

recursive("Hello world", 0)
3
Evan Fosmark