再帰関数に複数のreturn文がある時、どのreturnが返ってくるのかわからない。

Question

下記の関数は共に２４が返ってくるのはいいのですが、普通の再帰は終了条件でreturn 1で処理しているのに、なぜ１が返ってこないのか、わからないです。
末尾再帰の方は終了条件のaで返ってきているのに・・・・

階乗を普通の再帰で処理する

def fact(n):
    if n == 0: return 1
    return n * fact(n - 1)

fact(4)

階乗を末尾再帰で処理する

def fact(n, a = 1):
    if n == 0: return a
    return fact(n - 1, n * a)

fact(4)

Answer 1

末尾再帰ではないなら、呼び出し元で計算結果を返しますよね。
順番に追ってみればわかりますよ。

4 
-> 4 * fact(3)
-> 4 * 3 * fact(2)
-> 4 * 3 * 2 * fact(1)
-> 4 * 3 * 2 * 1 * fact(0)
-> 4 * 3 * 2 * 1 * 1

ちなみに末尾再帰はこうなってますよね。

4, 1
-> fact(3, 4 * 1)
-> fact(2, 3 * 4 * 1)
-> fact(1, 2 * 3 * 4 * 1)
-> fact(0, 1 * 2 * 3 * 4 * 1)
-> 1 * 2 * 3 * 4 * 1

Comments

[murata55atusi]

ご回答、ありがとうございます。
vscodeデバックのウォッチ式でステップ実行しながら、fact()の変化を見たのですが、よくわからなかったですが、一覧にして書き出していただくとわかりやすいですね。

Answer 2

実際にどうなっているのかわかるよう、コードを整形して、printを多めに入れてみました。

def fact(n):
    print("print1", n)
    if n == 0:
        x = 1  # 追いやすいように分ける（こっちは不要気味、下と合わせるため）
        print("print2", n, x)
        return x
    else:
        x = n * fact(n - 1)  # 追いやすいように分ける
        print("print3", n, x)
        return x

print(fact(4))
""" =>
print1 4
print1 3
print1 2
print1 1
print1 0
print2 0 1
print3 1 1
print3 2 2
print3 3 6
print3 4 24
24
"""

呼び出した子供が返るまで、親は待っている訳です。それだけ。

Comments

[murata55atusi]

ご回答、ありがとうございます。
printデバックも試してみます。

Answer 3

４ぐらいなら自分で動作を追いかけていけばいいんでは。
この入力のときにどう判断してなにが帰る、とか紙に書いていけば動作を理解できると思いますぜ

Comments

[murata55atusi]

ご回答、ありがとうございます。
一覧にして書き出すのが一番理解しやすいですね