Maximale Rekursionstiefe in Python überschritten

Question

Ich versuche, Power-Funktion durch Rekursion zu machen. Aber ich habe Laufzeitfehler wie Maximale Rekursionstiefe überschritten. Ich werde jede Hilfe zu schätzen wissen !! Hier ist mein Code.

def fast_power(a,n): 
    if(n==0): 
     return 1 
    else: 
     if(n%2==0): 
      return fast_power(fast_power(a,n/2),2) 
     else: 
      return fast_power(fast_power(a,n/2),2)*a 

Answer 1

sollten Sie n // 2 anstelle von n/2:

>>> 5 // 2 
2 
>>> 5/2 
2.5 

(zumindest in python3)

Das Problem ist, dass, sobald Sie mit Schwimmern am Ende dauert es eine ganze Weile, bis Sie am Ende bei 0 up durch 2 durch Dividieren:

>>> from itertools import count 
>>> n = 5 
>>> for i in count(): 
...  n /= 2 
...  if n == 0: 
...   break 
... 
>>> i 
1076 

So wie Sie sehen können, würden Sie mehr als 1000 rekursive Aufrufe benötigen, um 0 von 5 zu erreichen, und das ist oberhalb der Standard-Rekursionsbegrenzung. Außerdem: Dieser Algorithmus soll mit ganzen Zahlen betrieben werden.

---

Dies sagte ich, wie diese Funktion als etwas schreiben würde:

>>> fast_power(2, 7) 
128 
>>> fast_power(3, 7) 
2187 
>>> fast_power(13, 793) 
22755080661651301134628922146701289018723006552429644877562239367125245900453849234455323305726135714456994505688015462580473825073733493280791059868764599730367896428134533515091867511617127882942739592792838327544860344501784014930389049910558877662640122357152582905314163703803827192606896583114428235695115603966134132126414026659477774724471137498587452807465366378927445362356200526278861707511302663034996964296170951925219431414726359869227380059895627848341129113432175217372073248096983111394024987891966713095153672274972773169033889294808595643958156933979639791684384157282173718024930353085371267915606772545626201802945545406048262062221518066352534122215300640672237064641040065334712571485001684857748001990405649808379706945473443683240715198330842716984731885709953720968428395490414067791229792734370523603401019458798402338043728152982948501103056283713360751853 

Answer 2

I Erklärung des Problems unvollständig glauben @ Bakuriu lautet:

def fast_power(a, n): 
    if n == 0: 
     return 1 
    tmp = fast_power(a, n//2) 
    tmp *= tmp 
    return a*tmp if n%2 else tmp 

Welche produziert. Nicht seine Reimplementierung, sondern seine Erklärung des Fehlers. Sie könnten sich davon überzeugen, indem / mit // in Ihrem ursprünglichen Code zu ersetzen und versuchen:

fast_power(2, 2) 

es übersteigt nach wie vor den Stapel. Versuchen Sie, den Stapel zehnfach zu erweitern:

sys.setrecursionlimit(10000) 

es übersteigt immer noch den Stapel. Der Grund dafür ist, dass Sie auch eine infinte Schleife haben:

if (n % 2 == 0): 
    return fast_power(..., 2) 

Seit 2% 2 == 0, das hält einfach Rekursion für immer. Hinzufügen eines weiteren Basisfalls:

if n == 2: 
    return a * a 

behebt das Problem. Eine vollständige Lösung:

def fast_power(a, n): 
    if n == 0: 
     return 1 

# if n == 1: 
#  return a 

    if n == 2: 
     return a * a 

    if n % 2 == 0: 
     return fast_power(fast_power(a, n // 2), 2) 

    return a * fast_power(fast_power(a, n // 2), 2)