再帰と数学的帰納法の共通性？

質問

現在、アルゴリズムについて学んでいますが、
再帰についてわからないことがあります。

wikipedia"再帰"の項において、
( http://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0)

"数学的帰納法との原理的な共通性から、recursionの訳として数学では「帰納」を使うことがある。"

という記述があります。

再帰と数学的帰納法の原理的な共通性
というのが、どういうことかわかりません。

数学的帰納法については、大学受験に使う程度の知識です。(証明において、n=1で命題が成り立つことを示し、n=kで成立すると仮定し、n=k+1で成り立つことを示す等。)
再帰は関数を定義するのに、その関数自身を使うという認識です。

再帰と数学的帰納法の原理的な共通性とは何なのでしょうか？
ご教授お願いします。

回答No.4

oldman50 · ベストアンサー

数学的帰納法（mathematical induction）とは、命題Ｐ(ｎ）が全ての自然数ｎに対して成立することを証明する際に、

I）初期段階：
　その性質が０に対して成立することを証明する

II）帰納段階：
　その性質が自然数ｎについて成立するときに、自然数ｎ＋１に対しても成立することを証明する

という二段階に場合を分けて証明を行うことで、Ｐ(ｎ）が全ての自然数に対して成立することを証明する方法です。

（この方法が正しいことは、ペアノの公理に基づく自然数の定義から導かれます。）

　ところで、新しい数学的構造を定義する際に、似た様な方法をとることができます。
例えば、自然数ｎの階乗ｎ！を定義することを考えます。
　一般に、自然数ｎの階乗とは、自然数の集合Ｎから自然数の集合Ｎへの関数：　ｎ→ｎ！
という形で表されますが、その定義は、

I）初期段階：　ｎ＝０のとき、ｎ！＝１　とする。
II）帰納段階：　ｎ！が分っているとき、（ｎ＋１)！＝（ｎ＋１)・ｎ！　とする。

という二段階に場合を分けて定義を行うことで、自然数ｎの階乗ｎ！の定義が完結します。

このとき（II）の帰納段階では、左辺の（ｎ＋１)！を定義するのに右辺のｎ！を用いています。
すなわち、階乗！を用いて階乗！を定義しています。
　階乗！を表す関数をｆ：Ｎ→Ｎの形で表現すると、関数ｆ(ｎ）は、
　ｆ(ｎ）＝ｎ・ｆ(ｎ－１）
というふうに、自分自身を自分で再帰的（recursive）に呼ぶことによって、定義しています。

　このことを、当該のウィキペディアの頁では、recursion と「数学的帰納法との原理的な共通性」と呼んでいるのでしょう。

なお、初めに数学があり、後になって計算機科学ができました。
計算機科学では（II）の帰納段階のことを再帰的(recursive)定義と呼びますが、数学では帰納的(inductive)定義と呼びます。
帰納的はあくまでもinductiveです。recursiveが帰納的と約されることはありません。
ウィキペディアの頁の執筆者は、「再帰」の頁を見に来た人が「帰納」という言葉も参照できるように、リンクを貼ることが目的で、そのような表現を用いたのだと思います。

お礼

丁寧に回答していただいて有難うございます。
帰納と再帰について整理することができました。

回答No.3

cametan_42

再帰、って結局「プログラムで漸化式"自体を"書くこと」なんですよ。何も考えないで、漸化式を作る。
だから、漸化式と数学的帰納法が関連してる、的な軽い意味合いで「再帰と数学的帰納法の原理的な共通性」とか記述されてるんじゃないでしょうかね?

お礼

回答ありがとうございました。

回答No.2

koko_u_u

漸化式などの再帰的な定義に対して、数学的帰納法がよくマッチするだけで、
「原理的な共通性」と言えるようなものは特にないと思います。

因みに、私は数学的帰納法の原理とは「自然数の空でない部分集合には最小元が存在する」だと思っています。

お礼

回答ありがとうございました。

回答No.1

Tacosan

「より小さいところで成り立っている」ことを前提にして「大きなところでも成り立つ」とするところ, かな.

お礼

回答ありがとうございました。