現在、アルゴリズムについて学んでいますが、
再帰についてわからないことがあります。
wikipedia"再帰"の項において、
( http://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0)
"数学的帰納法との原理的な共通性から、recursionの訳として数学では「帰納」を使うことがある。"
という記述があります。
再帰と数学的帰納法の原理的な共通性
というのが、どういうことかわかりません。
数学的帰納法については、大学受験に使う程度の知識です。(証明において、n=1で命題が成り立つことを示し、n=kで成立すると仮定し、n=k+1で成り立つことを示す等。)
再帰は関数を定義するのに、その関数自身を使うという認識です。
再帰と数学的帰納法の原理的な共通性とは何なのでしょうか?
ご教授お願いします。
No.2
- 回答日時:
漸化式などの再帰的な定義に対して、数学的帰納法がよくマッチするだけで、
「原理的な共通性」と言えるようなものは特にないと思います。
因みに、私は数学的帰納法の原理とは「自然数の空でない部分集合には最小元が存在する」だと思っています。
No.4ベストアンサー
- 回答日時:
数学的帰納法(mathematical induction)とは、命題P(n)が全ての自然数nに対して成立することを証明する際に、
I)初期段階:
その性質が0に対して成立することを証明する
II)帰納段階:
その性質が自然数nについて成立するときに、自然数n+1に対しても成立することを証明する
という二段階に場合を分けて証明を行うことで、P(n)が全ての自然数に対して成立することを証明する方法です。
(この方法が正しいことは、ペアノの公理に基づく自然数の定義から導かれます。)
ところで、新しい数学的構造を定義する際に、似た様な方法をとることができます。
例えば、自然数nの階乗n!を定義することを考えます。
一般に、自然数nの階乗とは、自然数の集合Nから自然数の集合Nへの関数: n→n!
という形で表されますが、その定義は、
I)初期段階: n=0のとき、n!=1 とする。
II)帰納段階: n!が分っているとき、(n+1)!=(n+1)・n! とする。
という二段階に場合を分けて定義を行うことで、自然数nの階乗n!の定義が完結します。
このとき(II)の帰納段階では、左辺の(n+1)!を定義するのに右辺のn!を用いています。
すなわち、階乗!を用いて階乗!を定義しています。
階乗!を表す関数をf:N→Nの形で表現すると、関数f(n)は、
f(n)=n・f(n-1)
というふうに、自分自身を自分で再帰的(recursive)に呼ぶことによって、定義しています。
このことを、当該のウィキペディアの頁では、recursion と「数学的帰納法との原理的な共通性」と呼んでいるのでしょう。
なお、初めに数学があり、後になって計算機科学ができました。
計算機科学では(II)の帰納段階のことを再帰的(recursive)定義と呼びますが、数学では帰納的(inductive)定義と呼びます。
帰納的はあくまでもinductiveです。recursiveが帰納的と約されることはありません。
ウィキペディアの頁の執筆者は、「再帰」の頁を見に来た人が「帰納」という言葉も参照できるように、リンクを貼ることが目的で、そのような表現を用いたのだと思います。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 数学的帰納法の質問です。 n=1、k,k+1のときすべての自然数nが成り立つという証明で、なぜ、n= 7 2023/07/02 11:59
- 数学 『◯と●の帰納法』 2 2023/04/19 20:57
- 数学 数学的帰納法について質問があります。 8 2023/04/05 23:32
- 数学 帰納法 2 2022/06/08 22:25
- 数学 『数学的帰納法のトリセツ』 4 2022/06/06 07:34
- 統計学 加重最小二乗法=①「変数を自然対数変換」=②「誤差項の分散の逆数を重み付け」? 8 2022/11/26 11:15
- 数学 全ての自然数nに対して「2^3n−3^n」は5の倍数であることを数学的帰納法で証明 写真の解法は合っ 2 2023/06/18 00:30
- 数学 帰納法 3 2022/06/08 22:24
- 消費者問題・詐欺 帰納法 2 2022/06/09 21:08
- 統計学 t統計量とF統計量について 9 2023/01/05 14:23
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
中2です笑 証明の問題がどうし...
-
ミラー指数:面間隔bを求める公...
-
勉強のことをかんがえる
-
(命題) 三角形の内角のうち少...
-
a>b>0 c>d>0 ac>bdの証明のや...
-
写像の問題です
-
死後の世界はない[無]になる...
-
2つの奇数の和は偶数になる。そ...
-
6は何乗しても下一桁が6
-
x>0かつy>0の否定 わかる方教え...
-
強い思念が脳から電磁波として...
-
証明の終わりは、「よって題意...
-
計算式について教えてください。
-
a,b,cを整数とする。 a^2+b^2=c...
-
過去質『すべての自然数とすべ...
-
lim(an-bn)=0 lim an=α ならば ...
-
ma=Fは数学で証明されていない?
-
ゼウスが居たとしたら何年前に...
-
数学1 背理法について
-
二項定理を用いて、つぎのこと...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
中2です笑 証明の問題がどうし...
-
過去質『すべての自然数とすべ...
-
理論と原理の違い
-
計算式について教えてください。
-
ミラー指数:面間隔bを求める公...
-
キノの旅「・・・・あなたが正...
-
天国や、極楽浄土は、あるので...
-
証明の終わりは、「よって題意...
-
在学証明書ってなんですか?
-
日本で神道と仏教はどちらが先...
-
東京都小池百合子知事の学歴詐...
-
血統書付きの種、という表現は...
-
認定書と証明書の違い
-
原理と理論の違いを教えてくだ...
-
二項定理を用いて、つぎのこと...
-
証明書の開封無効
-
数学の記述の書き方 数学でaとb...
-
数学の逆裏対偶の、「裏」と、...
-
奨学金の保証人、別生計の意味は?
-
窒息について
おすすめ情報