Konvertieren einer Funktion mit zwei rekursiven Aufrufe in eine interative Funktion

Question

Ich habe eine Funktion, die zwei rekursive Aufrufe hat, und ich versuche, es in eine iterative Funktion zu konvertieren. Ich habe es herausgefunden, wo ich es mit einem Anruf ziemlich leicht tun kann, aber ich kann nicht herausfinden, wie man den anderen Anruf einbaut.

die Funktion:

def specialMultiplication(n): 
    if n < 2: 
     return 1 
    return n * specialMultiplication(n-1) * specialMultiplication(n-2) 

Wenn ich nur einer von ihnen hatte, wäre es wirklich einfach sein:

def specialMult(n, mult = 1): 
    while n > 1: 
     (n, mult) = (n-1, n * mult) # Or n-2 for the second one 
    return mult 

Ich kann einfach nicht herausfinden, wie der zweite Anruf hinzuzufügen, um bekomme die richtige Antwort insgesamt. Vielen Dank!

Answer 1

Wenn es Ihnen nichts ausmacht, die Struktur Ihres Algorithmus ein wenig mehr zu ändern, können Sie die Werte von unten nach oben berechnen, beginnend mit den kleinsten Werten.

def specialMultiplication(max_n): 
    a = b = 1 
    for n in range(1, max_n+1): 
     a, b = b, a*b*n 
    return b 

Answer 2

Konvertieren Sie die Rekursion auf eine iterative Funktion eines Hilfs "ToDo-Liste" mit:

def specialMultiplication(n): 
    to_process = [] 
    result = 1 
    if n >= 2: 
     to_process.append(n) 
     while to_process: # while list is not empty 
      n = to_process.pop() 
      result *= n 
      if n >= 3: 
       to_process.append(n-1) 
       if n >= 4: 
        to_process.append(n-2) 
    return result 

1. eine Arbeitsliste erstellen (to_process)
2. wenn n >= 2, fügen n zur Liste
3. während ist nicht leer, Pop-Element aus Liste, multiplizieren, um
4. zu ergeben, wenn n-1 < 2, nicht pe rform „links“ Betrieb (lassen Sie dabei die Liste arbeiten)
5. wenn n-2 < 2, nicht durchführen „richtigen“ Operation (anhängen nicht Liste arbeiten)

Diese Methode den Vorteil des Konsums hat weniger Stapel. Ich habe die Ergebnisse gegen rekursive Version für Werte von 1 bis 25 überprüft und sie waren gleich.

Beachten Sie, dass es immer noch langsam ist, da die Komplexität O(2^n) ist, so dass es langsam von n=30 langsam wird (die Zeit verdoppelt sich, wenn n um 1 zunimmt). n=28 wird in 12 Sekunden auf meinem Laptop berechnet.

Ich habe erfolgreich diese Methode verwendet, um ein Stack-Overflow-Problem zu beheben, wenn Sie einen Flood-Fill-Algorithmus ausführen: Fatal Python error: Cannot recover from stack overflow. During Flood Fill aber hier Blcknght Antwort ist besser angepasst, weil es die Art der Berechnung von Anfang an neu überdenkt.

Answer 3

Die Funktion des OP hat die gleiche rekursive Struktur wie die Fibonacci und Lucas Funktionen, nur mit unterschiedlichen Werten für f0, f1, und g:

f(0) = f0 
f(1) = f1 
f(n) = g(f(n-2), f(n-1), n) 

Dies ist ein Beispiel eines recurrence relation. Hier ist eine iterative Version der allgemeinen Lösung, die f (n) in n Schritten berechnet. Es entspricht einer Bottom-Up-Tail-Rekursion.

def f(n): 
    if not isinstance(n, int): # Can be loosened a bit 
     raise TypeError('Input must be an int') # Can be more informative 
    if n < 0: 
     raise ValueError('Input must be non-negative') 
    if n == 0: 
     return f0 
    i, fi_1, fi = 1, f0, f1 # invariant: fi_1, fi = f(i-1), f(i) 
    while i < n: 
     i += 1 
     fi_1, fi = fi, g(fi_1, fi, n) # restore invariant for new i 
    return fi 

Blckknight Antwort ist eine vereinfachte Version dieses