Ausbeute in Rekursion Multiplayer

Question

ich habe gerade diese Funktion geschrieben und Fehler vom Interpreter bekommen "RekursionError: maximale Rekursionstiefe im Vergleich überschritten" ist es möglich, Ausbeute in dieser Rekursion zu verwenden?

def multiplyer(fir, sec): 
    if(sec==1): 
     return fir 
    else: 
     return fir+multiplyer(fir, sec-1) 
print(multiplyer(5, 2983)) 

Answer 1

Es besteht keine Notwendigkeit yield überhaupt zu benutzen (und soweit ich weiß, wird es sowieso nicht funktionieren). Ihre multiplayer Funktion ist nur äquivalent zu:

def multiplayer(fir,sec): 
    return fir*sec 

weiterhin yield wird nicht viel Unterschied machen, da sie nach wie vor in einem Rekursionsfehlers führen wird: Schließlich werden Sie noch Anrufe 2983 tief durchführen (was für den Anruf in der Regel zu viel Stapel). Python unterstützt auch Tail Recursion Optimization (TRO) nicht.

yield wird verwendet, wenn Sie einen Generator verwenden möchten. Ein Generator erzeugt mehrere Werte (es können null, eins oder mehrere sein). Hier benötigen Sie jedoch einen einzelnen Wert (und Sie benötigen es sofort). jedoch sagen, dass Sie yield wie verwenden:

def multiplyer(fir, sec): 
    if(sec==1): 
     yield fir 
    else: 
     yield fir+next(multiplyer(fir, sec-1)) 

print(next(multiplyer(5, 2983))) 

wird es keinen Unterschied machen: Sie werden immer noch die Rekursion und das gebundene zu erreichen.

Answer 2

Wenn mit Rekursion tun haben, können Sie die maximal zulässige überprüfen Rekursionstiefe wie:

import sys 
sys.getrecursionlimit() 

und das Schöne daran ist, dass Sie es auch einstellen:

sys.setrecursionlimit(3000) 

Allerdings sagt dies nichts über Ihr Code oder wenn es optimal für das ist, was Sie erreichen möchten.

Answer 3

Sie haben keinen Speicherplatz mehr im Stapel, da Sie die Funktion sich 2983 mal nennen lassen, was bedeutet, dass Sie die Anzahl der Rückgabeadressen und Argumente auf dem Stapel speichern, was nicht sinnvoll ist.

Wenn Ihre Anforderung Rekursion zu verwenden ist, können Sie die Rekursionstiefe O (log n) um, indem Sie diese reduzieren:

def multiplyer(fir, sec): 
    if sec==1: 
     return fir 
    elif sec==0: 
     return 0 
    else: 
     return multiplyer(fir, sec//2) + multiplyer(fir, (sec+1)//2) 
print(multiplyer(5, 2983)) 

Oder effizienter, auch die Anzahl der rekursiven Aufrufe zu Reduzierung O (log n) Reihenfolge:

def multiplyer(fir, sec): 
    if sec==0: 
     return 0 
    elif sec%2 == 0: 
     return 2 * multiplyer(fir, sec//2) 
    else: 
     return fir + 2 * multiplyer(fir, sec//2) 
print(multiplyer(5, 2983)) 

Answer 4

nicht Rekursion in Python verwenden, wo Iteration tun. Generatoren optimieren für Speicher Nutzung, sonst nichts. Sie sind langsamer als die Alternativen und bieten keine Problemumgehungen für das globale Rekursionslimit (was tatsächlich eine Begrenzung für die Größe des Aufruf-Stacks darstellt; nicht-rekursive Aufrufe zählen ebenfalls zum Limit).

# Just demonstrating the conversion from recursion to iteration. 
# fir * sec would be the most efficient solution. 
def multiplyer(fir, sec): 
    rv = 0 
    while sec > 0: 
     rv += fir 
     sec -= 1 
    return rv