質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.02%
ループ

ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

関数

関数(ファンクション・メソッド・サブルーチンとも呼ばれる)は、はプログラムのコードの一部であり、ある特定のタスクを処理するように設計されたものです。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

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

kay_ventris4
kay_ventris4

総合スコア264

ループ

ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

関数

関数(ファンクション・メソッド・サブルーチンとも呼ばれる)は、はプログラムのコードの一部であり、ある特定のタスクを処理するように設計されたものです。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

4回答

0グッド

0クリップ

1526閲覧

投稿2021/03/29 06:03

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

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 の代わりに空リスト [] を返すものがあったりなどがありましたが、なぜこれだけで無限ループを回避したことになるのでしょうか?素人質問で恐縮ですが、ご教授お願い申し上げます。

以下のような質問にはグッドを送りましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

グッドが多くついた質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

maisumakun

2021/03/29 06:16

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

回答4

2

ベストアンサー

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

投稿2021/03/29 06:18

jeanbiego

総合スコア3964

miyabi_takatsuk, kay_ventris4👍を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

kay_ventris4

2021/03/29 06:21

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

1

例えば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
seastar3

総合スコア2285

kay_ventris4👍を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

kay_ventris4

2021/03/29 06:28

ありがとうございます。 勉強になりました。

1

実際は無限ループを回避するためにこのような条件分岐が与えられているとのことですが

そのとおりです。正しく実装しなかった再帰関数は、無限の再帰を続ける事態に陥ります。

投稿2021/03/29 06:19

maisumakun

総合スコア141508

kay_ventris4👍を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

maisumakun

2021/03/29 06:20

> なぜこれだけで無限ループを回避したことになるのでしょうか? 逆に「ただ0を返す」だけのパスが、どうして無限ループになるとお考えでしょうか?
kay_ventris4

2021/03/29 06:23 編集

再帰がreturn 0の部分でも行われると勘違いしておりました。

1

再帰関数とか難しく考えすぎです。
素直に、そいつがどういう動作をするのか順番に追いかけていけば済むことです

n に2を渡したとき、3を渡したとき、どういう動作をするのか追いかけてみましょう。

んで、nにマイナスの値を入れたときにはどういう動作になるのか考えてみましょう

投稿2021/03/29 06:11

y_waiwai

総合スコア86062

kay_ventris4👍を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

kay_ventris4

2021/03/29 06:21

ありがとうございます。

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.02%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

ループ

ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

関数

関数(ファンクション・メソッド・サブルーチンとも呼ばれる)は、はプログラムのコードの一部であり、ある特定のタスクを処理するように設計されたものです。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。