再帰関数は本当に無限ループじゃない？

#用いた関数
再帰関数という言葉を知り、その内容を調べていたところ、以下のような関数を見つけました：

PYthon
1def total(n):
2    if n < 1:
3        return 0
4    return n + total(n - 1)

疑いもなく、n に例えば 100 を渡せば 5050 が出力され、1 ~ nまでの総和を出力する関数として正常に動いています。

#質問
再帰関数とは何か、どうして動くのか、といったことは既に他の例を見て理解したのですが、上記コード中の return 0 の箇所について、これは n < 1 となった全ての n (-100, -1000, -10000, ...)に対して 0 を返し続けるというある種の無限ループに陥っているのではないか？という疑問が湧きました（実際は無限ループを回避するためにこのような条件分岐が与えられているとのことですが）。他の再帰関数の実装例でも、0 の代わりに空リスト [] を返すものがあったりなどがありましたが、なぜこれだけで無限ループを回避したことになるのでしょうか？素人質問で恐縮ですが、ご教授お願い申し上げます。

maisumakun

2021/03/29 06:16

> n < 1 となった全ての n (-100, -1000, -10000, ...)に対して 0 を返し続けるというある種の無限ループに陥っているのではないか？という疑問が湧きましたどういう意味でしょうか？

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

回答4件

ベストアンサー

return文が2つあり、
return n + total(n - 1)は確かにtotalを呼び出してるので再帰になってますが、
return 0はtotalを呼び出していないことに注意してください。

投稿2021/03/29 06:18

jeanbiego

総合スコア3966

kay_ventris4

2021/03/29 06:21

return 0 に再帰の要素はなくここで中断されるということだったんですね。スッキリしました。ありがとうございます。

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

例えばn=3のとき、
戻ってくるものは、
toatal(3 + total(2 + total(1 + total(0))))
total(0)=0なので、
答は、6です。
機械語レベルで、各関数の作業場所の先頭番地がLIFO方式でスタックされて、n=0まで行くわけです。そして、n=0のときに跳ね返ることが許されて、スタックがほどかれていき、答が決まります。
したがって、お考えのように無限ループ的に各関数がスタックを重ねていけば、メモリーオーバーも起こりえますが、if n < 0: がない場合、スタックオーバーフローエラーで停止するのです。

投稿2021/03/29 06:25

編集2021/03/29 06:30