Ist diese Funktion rekursiv, obwohl sie sich nicht nennt?

from pythonds.basic.stack import Stack rStack = Stack() def toStr(n,base): convertString = "0123456789ABCDEF" while n > 0: if n < base: rStack.push(convertString[n]) else: rStack.push(convertString[n % base]) n = n // base res = "" while not rStack.isEmpty(): res = res + str(rStack.pop()) return res print(toStr(1345,2)) 

Ich beziehe mich auf dieses Tutorial und habe auch den Code oben eingefügt. Das Tutorial sagt, dass die Funktion rekursiv ist, aber ich sehe keinen rekursiven Anruf irgendwo, nur eine Weile Schleife. Was vermisse ich?

3 Solutions collect form web for “Ist diese Funktion rekursiv, obwohl sie sich nicht nennt?”

Sie haben Recht, dass diese Funktion nicht rekursiv ist. Allerdings ist der Kontext, dass auf der vorherigen Folie gab es eine rekursive Funktion, und in diesem wollen sie einen Einblick, wie es sich intern verhält zeigen . Sie sagen später:

Das vorhergehende Beispiel [dh das in Frage – B.] gibt uns einen Einblick, wie Python einen rekursiven Funktionsaufruf implementiert.

Also, ja, der Titel ist irreführend, es sollte eher sein, eine rekursive Funktion zu erweitern oder das rekursive Funktionsverhalten mit einem Stapel oder so ähnlich zu impfen.

Man kann sagen, dass diese Funktion einen rekursiven Ansatz / eine Strategie in gewissem Sinne einsetzt, um das Problem zu lösen, ist aber nicht rekursiv.

Ein rekursiver Algorithmus ist definitionsgemäß eine Methode, bei der die Lösung eines Problems von Lösungen für kleinere Instanzen desselben Problems abhängt .

Hier ist das Problem, eine Zahl in einen String in einer gegebenen Notation umzuwandeln.

Die "Lagerung" der Daten sieht die Funktion eigentlich so aus:

 push(d1) push(d2) ... push(dn-1) push(dn) res+=pop(dn) res+=pop(dn-1) ... res+=pop(d2) res+=pop(d1) 

Was effektiv ist:

 def pushpop(): push(dx) pushpop(dx+1...dn) res+=pop(dx) 

Dh ein Schritt, der einen bestimmten Teil der Daten verarbeitet, umschließt alle Schritte, die den Rest der Daten verarbeiten (wobei jedes Stück auf die gleiche Weise verarbeitet wird).

Es kann argumentiert werden, wenn die Funktion rekursiv ist (da sie dazu neigen, den Begriff auf Unterroutinen im engeren Sinne anzuwenden), aber der Algorithmus, den es definitiv implementiert, ist.


Für Sie, um den Unterschied besser zu fühlen, hier ist eine iterative Lösung für das gleiche Problem:

 def toStr(n,base): charmap = "0123456789ABCDEF" res='' while n > 0: res = charmap[n % base] + res n = n // base return res 

Wie Sie sehen können, hat diese Methode viel weniger Speicherplatz, da sie keine Aufgaben auflädt . Dies ist der Unterschied: Ein iterativer Algorithmus führt jeden Schritt mit der gleichen Instanz des Zustands durch Mutation aus , während ein rekursiver eine neue Instanz für jeden Schritt erstellt , die sie zwangsläufig auflagern, wenn die alten noch benötigt werden.

Weil du eine Stackstruktur verwende.

Wenn Sie überlegen, wie Funktionsaufruf implementiert ist, ist Rekursion im Wesentlichen ein einfacher Weg, um den Compiler zu einem Stapel von Aufrufen für Sie zu verwalten.

Diese Funktion macht alle Stack-Handhabung manuell, aber es ist immer noch konzeptionell eine rekursive Funktion, nur eine, wo das Stack-Management manuell statt statt der Compiler tun es tun.

  • N-Queen-Backtracking in Python: Wie gibt man Lösungen zurück, anstatt sie zu drucken?
  • Python rekursiv anhängen Liste Funktion
  • Kreuz Produkt von Sets mit Rekursion
  • Rekursionsfunktion funktioniert nicht richtig
  • Was ist die maximale Rekursionstiefe in Python und wie man es erhöht?
  • Refactoring rekursive "Vorkommen von" Funktion
  • Python Recursive Funktion fehlende Ergebnisse
  • Python recursion return Keine Typ
  • Rekursive Funktion gibt keine in Python zurück [doppelte]
  • Python-Funktion kehrt nach Rekursion nicht zurück
  • Baktracking-Funktion, die die Berechnung berechnet, überschreitet die maximale Rekursionstiefe
  • Python ist die beste Programmiersprache der Welt.