funkcja rekursywna python, która drukuje od 0 do n?

Question

Próbuję napisać funkcję rekurencyjną, która drukuje od 0 do n, ale nie mam pojęcia, jak to zrobić. Przypadkowo wykonana z jednego, który drukuje chociaż n 0:

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

Nie wiem, czy to pomaga, czy nie, może uda mi się coś zmienić z kodem, aby przejść od 0 do n?

Answer 1

Prawie got it!oto stała, uproszczona wersja:

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

Zauważ, że:

• Nie trzeba powrócić nic z funkcji rekurencyjnej, że tylko drukuje ceni
• Do drukowania w kolejności rosnącej The print oświadczenie musi być umieszczone po po rekursywnym wywołaniu
• Rekursja kończy się, gdy n < 0, biorąc pod uwagę, że drukujemy, nie ma już nic do zrobienia terwards i to jest ok, aby powrócić None (wartość domyślna powrót Pythona)

UPDATE

Wydaje się, że pisanie ogon rozwiązanie rekurencyjne jest modne tutaj :) no cóż, tu jest mój strzał w nim , uproszczona i ogon wersja rekurencyjna użytkownika @ AndyHayden pomysł - za pomocą połączenia ogon optymalizacji dekorator recipe:

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

tak czy inaczej, to działa zgodnie z oczekiwaniami:

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

Answer 2

Można wymienić 0 i N, a + z - aby dokonać rekurencyjną funkcję odliczania do rekurencyjnego odliczanie zegara:

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

i nazywają to następująco:

countup(3) 

@JFSebastian zwraca uwagę, że ten algorytm ma tę zaletę, że jest O (1), a nie O (n), jak omówiono w tym excellent article o różnicy między liniową i iteracyjną rekurencją, jeśli jest używana z dekoratorem @tail_call_optimized.

Answer 3

Około 99%.

Pomyśl o swojej podstawowej sprawie i rekurencyjnym kroku - kiedy uderzysz 0, co chcesz zrobić? Gdy nadal pracujesz w dół od n, co chcesz zrobić?

Jeśli odwrócisz kolejność drukowania wartości, osiągniesz pożądany wynik.

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

Powodem tego jest to, że wywołania rekursywne idą na stosie wywołań. Gdy przekierowujesz połączenia na stos, gdy nie ma mowy o skrzynce końcowej, będziesz kontynuował dodawanie kolejnych połączeń, aż dotrzesz do podstawowego przypadku o numerze n == 0, a następnie zaczniesz drukować wyłącznie wartości.

Pozostałe wywołania będą następnie przesyłane do instrukcji drukowania, ponieważ ich wykonanie powróciło do wiersza po warunku.

Więc wywołanie stosu wygląda mniej więcej tak:

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