再帰で階乗に挑戦してみる

こんばんは。
初心者なりに挑んでみたので
皆様の参考になれば幸いです。

例えばですが、3!(=3 * 2 * 1) を実現するにはどうすれば良いでしょうか。

print(3*2*1)

出来ました(笑)!
じゃあ、def を使って、こんな風に書いてみたらどうでしょうか。

test.py

def test(n:int=3):
    if n>1:
        return n * test(n-1)
    else:
        return 1

print(test())

取り急ぎ初期値 3 でやってみました。
取りあえず、一個一個代入してみてみましょう。
まずは n == 3 の時です。

test.py

# n == 3 のとき
def test(n:int=3):
    #n == 3 なので、if の中に入ります 
    if n>1:
       #return 3 * test(3-1)
        return n * test(n-1)
    else:
        return 1

print(test())

やった。return が来たから抜けられる!! っと思いきや、
3 * test(2) !?
test(2) が分からないと終われないですね。
仕方ありません。
良くわからないですが、n == 2、つまり test(2) を考えてみましょう。

test.py

# n == 2 のとき
def test(n:int=2):
    #n == 2 なので、if の中に入ります 
    if n>1:
       #return 2 * test(2-1)
        return n * test(n-1)
    else:
        return 1

print(test())

ん!? return 2 * test(1) !?
またもや test() が現れましたが、今度は test(1) です。
仕方ない、test(1) もやってみましょう。

test.py

# n == 1 のとき
def test(n:int=1):
    if n>1:
        return n * test(n-1)
    #n == 1 なので、else の中に入ります 
    else:
        # 1 を返します
        return 1

print(test())

取りあえず、n==1 の時は return 1 なので、
答えが 1 であることがわかりました。
よかった、やっと整数に会えた(笑)

一旦整理しましょう。

図にあるように n==3 を実行したら、n==2 が現れて、更に n==1 が現れました。
イメージとしては test(2) の中に 2 * test(1) が埋め込まれていて、
test(1) の中に 1 * test(0) が埋め込まれているようです。

今分かっているのは、1 * test(0) が 1 * 1 、
つまり 1 であることだけです。

よし、3 * test(2) は一旦、無視し、
下図中央の 2 * test(1) の test(1) に 1 * test(0) を代入してみましょう。

2 * test(1) == 2 * {1 * test(0)} なので、2 * 1 = 2 であることが分かります。
ってことは。。。

3 * test(2) == 3 * {2 * test(1)} == 3 * {2 * 1} になりましたね。
これで何とか 3! を表現することが出来ました。

以上のように、ある事象に、自身を含んでいた場合、
再帰的であるというそうです。

この考え方を使うと 3! だけでなく、n の階乗も勿論、表現できます。
シンプルな記述ですが、ちゃんと考えると複雑だったりして
中々、面白かったです、お疲れ様でした(≧▽≦)。

その他の記事
スタックをPythonで書いてみた
1つの配列に 2 つのスタックを Python で実装してみる
Python で作ったスタックに最小値(min) を返す機能を追加するが push/pop/min は基本 O(1) !!