0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Last updated at Posted at 2020-09-28

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

例えばですが、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 であることがわかりました。
よかった、やっと整数に会えた(笑)

一旦整理しましょう。
図1.PNG
図にあるように 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.PNG
2 * test(1) == 2 * {1 * test(0)} なので、2 * 1 = 2 であることが分かります。
ってことは。。。
図3.PNG
3 * test(2) == 3 * {2 * test(1)} == 3 * {2 * 1} になりましたね。
これで何とか 3! を表現することが出来ました。

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

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

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?