python - 0からnまで出力するpython再帰関数?

Question

0からに出力する再帰関数を作成しようとしていますnが、その方法がわかりません。nから印刷するものを誤って作成しまし0た：

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

それが役立つかどうかはわかりませんが、コード内の何かを変更して から に変更できます0かn?

Answer 1

あなたはそこに約99％います。

基本ケースと再帰ステップについて考えてみてください。0 になったら、何をしたいですか? からまだ下に向かっているときn、何が起こりたいですか?

値を出力する順序を逆にすると、目的の結果が得られます。

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

これが機能する理由は、再帰呼び出しが呼び出しスタックに移動するためです。呼び出しをスタックにプッシュすると、最終ケースが満たされていなくても、基本ケースの に到達するまでさらに呼び出しを追加し続けn == 0、その後、値の出力のみを開始します。

他の呼び出しは、実行が条件の後の行に戻るため、print ステートメントにフォールスルーします。

したがって、コール スタックは次のようになります。

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

Answer 2

0 と n、および + を - に置き換えて、再帰カウントダウン関数を再帰カウントアップにすることができます。

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

そして、次のように呼び出します。

countup(3)

@JFSebastian は、このアルゴリズムには、O(n) ではなく O(1) であるという利点があると指摘しています。これは、この優れた記事で説明されているように、線形再帰と反復再帰の違いについて、@tail_call_optimizedデコレーターと共に使用した場合です。