Python rekursive Funktion, die von 0 bis n druckt?

Question

Ich versuche, eine rekursive Funktion zu schreiben, die von 0 bis n druckt, aber ich habe keine Ahnung, wie es geht. Ich habe aus Versehen einen gemacht, die allerdings auf 0 von n druckt:

def countdown(n): 
    print(n) 
    if n == 0: 
     return 0 
    return countdown(n - 1) 

Ich weiß nicht, ob das hilft oder nicht, vielleicht kann ich etwas von dem Code ändern, um es von 0 bis n gehen zu machen?

Answer 1

Sie es fast bekam!hier ist eine feste, vereinfachte Version:

def countup(n): 
    if n >= 0: 
     countup(n - 1) 
     print(n) 

Beachten Sie, dass:

• Sie haben noch nichts von einer rekursiven Funktion zurückzugeben, die nur drucken Werte
• Für den Druck in aufsteigender Reihenfolge der print Anweisung muss platziert werden nach der rekursive Aufruf
• Die Rekursion beendet, wenn n < 0, da wir nur drucken, gibt es nichts zu tun af terwards und es ist in Ordnung zurückzukehren None (Python-Standardrückgabewert)

UPDATE

Es scheint, dass ein Schwanz rekursive Lösung Schreiben ist die ganze Wut hier :) na ja, hier ist mein Schuss auf ihn , eine vereinfachte und Schwanz-rekursive Version von @ AndyHayden Idee - mit dem Schwanz Call-Optimierung Dekorateur recipe:

@tail_call_optimized 
def countup(N, n=0): 
    print(n) 
    if n < N: 
     countup(N, n + 1) 

so oder so, es funktioniert wie erwartet:

countup(5) 
=> 0 
    1 
    2 
    3 
    4 
    5 

Answer 2

Sie können die 0 und die n ersetzen, und die + mit a - Ihre rekursive Countdown-Funktion zu einer rekursiven countup zu machen:

def countup(N, n=0): 
    print(n) 
    if n == N: 
     return 
    return countup(N, n + 1) 

Und es nennen wie folgt:

countup(3) 

@JFSebastian weist darauf hin, diesen Algorithmus hat den Vorteil, O (1) ist, statt O (n), wie in diesen excellent article über den Unterschied zwischen einem linearen und iterativer Rekursion diskutiert, wenn sie mit dem @tail_call_optimized decorator verwendet.

Answer 3

Sie sind etwa 99% gibt.

Denken Sie an Ihrem Basisfall und Ihren rekursive Schritt - wenn Sie 0 getroffen, was willst du tun? Wenn du dich immer noch von n runter arbeitest, was willst du dann?

Wenn Sie die Reihenfolge umkehren, in dem Sie den Wert drucken, erhalten Sie das gewünschte Ergebnis erreichen.

def countdown(n): 
    if n != 0: 
     countdown(n-1) 
    print(n) 

Der Grund dafür ist, dass rekursive Aufrufe auf den Aufrufstack gehen. Wenn Sie Anrufe auf den Stapel schieben, während Ihr Endfall nicht erreicht wird, fügen Sie weitere Anrufe hinzu, bis Sie Ihren Basisfall n == 0 erreichen, und Sie beginnen dann ausschließlich mit dem Drucken der Werte.

Die anderen Anrufe werden dann bis in die print-Anweisung fallen, da ihre Ausführung auf der Linie nach dem bedingten zurückgekehrt ist.

Also, der Call-Stack sieht dies so etwas wie:

countdown(5) 
    countdown(4) 
     countdown(3) 
      countdown(2) 
       countdown(1) 
        countdown(0) 
        print(0) 
       print(1) 
      print(2) 
     print(3) 
    print(4) 
print(5)