この関数がどんなふうに再帰的定義されているかを知りたい

下のコードがどんなふうに再帰的定義されているかを解説して欲しいです。できれば再帰に関する説明もお願いします。

Python
コード
def dict(str, depth):
  if depth == 0:
    return
  print(str)
  dict(str+'a', depth-1)
  dict(str+'b', depth-1)

n=4
dict('', n)

y_waiwai

2020/10/13 13:37

どこから持ってきたコードなんでしょうか

行動規範の内容に同意します

回答3件

ベストアンサー

呼び出し階層

dict(, 4)
  dict(a, 3)
    dict(aa, 2)
      dict(aaa, 1)
        dict(aaaa, 0)
        dict(aaab, 0)
      dict(aab, 1)
        dict(aaba, 0)
        dict(aabb, 0)
    dict(ab, 2)
      dict(aba, 1)
        dict(abaa, 0)
        dict(abab, 0)
      dict(abb, 1)
        dict(abba, 0)
        dict(abbb, 0)
  dict(b, 3)
    dict(ba, 2)
      dict(baa, 1)
        dict(baaa, 0)
        dict(baab, 0)
      dict(bab, 1)
        dict(baba, 0)
        dict(babb, 0)
    dict(bb, 2)
      dict(bba, 1)
        dict(bbaa, 0)
        dict(bbab, 0)
      dict(bbb, 1)
        dict(bbba, 0)
        dict(bbbb, 0)

投稿2020/10/14 03:08

編集2020/10/14 03:14

ozwk

総合スコア13553

ロシアの民芸品、マトリョーシカ人形をイメージすると分かりやすいと思います。
人形の中に人形が入っていて、中の人形の中にも人形が入っていて。。。

質問の中に記載いただいたコードではdict()という名前の関数を定義しています。
このdict()という関数の定義の中にもdict()が使われていますよね。
dict()という関数を定義の中のdict()の中でも当然、dict()が使われます。

どうでしょう。マトリョーシカ人形みたいじゃないですか？

このように、定義した関数の中で、その関数自体を使っている（呼び出している）ような関数を再帰的な関数と言います。

こういう関数を定義する時に大切なのは、挙げていただいたコードの場合だと、

Python
1if depth == 0:
2    return

この部分になります。あとは、関数の中で関数を呼び出している時の引数をdepth-1としている点です。
これによって、呼び出す回数に制限をかけています。

マトリョーシカ人形に例えると、中に入れる人形の数を制限する、というイメージでしょうか。

挙げていただいたコードの場合、n=4としているので、中に入れる人形を4体に制限した、のようなイメージです。

呼び出す回数に制限をかけないと、永遠と関数を呼び出し続けるので、プログラムの実行が終わらずに、最終的にはエラー（RecursionError）となります。

マトリョーシカ人形でも、中に入れる人形の数を決めないと、100体、1000体と中に人形を入れ続けないといけないので、大変なことになります。

そのため、再帰的な関数を定義する場合、呼び出す回数に制限をかけることが重要になります。

マトリョーシカ人形に例えてみましたが、いかがでしょうか？
これで理解が深まれば幸いです。

追記

マトリョーシカ人形、撃沈。。。
気を取り直して、図にしてみました。

式にすると、

dict_4 = dict_a3 + dict_b3

dict_a3 = dict_aa2 + dict_ab2
dict_b3 = dict_ba2 + dict_bb2

dict_aa2 = dict_aaa1 + dict_aab1
dict_ab2 = dict_aba1 + dict_abb1
dict_ba2 = dict_baa1 + dict_bab1
dict_bb2 = dict_bba1 + dict_bbb1

こんなイメージでしょうか？

分かりやすくなったか、自信はないですが、さらに理解が深まることに寄与できれば幸いです。

投稿2020/10/13 14:20

編集2020/10/14 04:52