再帰を理解するために、帰納的定義を知る。

数学的帰納法

「全ての自然数に対して、性質Pが成立する」ことを示すための推論法。
まず、「P(0)」が成立することを示す。次に「__P(x)__を仮定して、__P(x + 1)__を示す」ことにより、「__全ての自然数n__に対して、__P(n)__が成立する」ことが言える、という推論である。

しかし、帰納法は自然数に対する推論法だけではない。自然数以外にも、リストや木などの集合を「帰納的に定義」することができ、それぞれに対する推論法としての帰納法がある。

実は、数学的に厳密な意味で、無限に多くの要素を持つ集合を作り出したり、無限に多くの要素に対する性質を示す方法というのは、それほどたくさんあるわけではない。むしろ、そのような定義、推論方法は、ほとんどの場合__帰納__によると言える。

帰納的に定義された集合

__自然数の集合__などの無限集合を厳密に定義するために、帰納的定義(inductive definition)を用いる。

• basis 基礎
  • いくつかのもの（あらかじめわかっているもの）は、集合Aの要素であることを定める。
• induction step ステップ
  • すでにAの要素であることがわかっているものから、新たにAの要素を作る操作を定める。
• closure 限定句
  • 上の操作を、有限回適応して作られた要素のみがAの要素であると定める。

帰納的定義では、closure条件を常に必要とするので、省略して書かないことが多い。
closure条件がないと、集合Aが一意に定まらない。

所感

__再帰__を理解するには帰納的な定義における、__closure条件__が重要になってくる。限定句がない状況では無限ループになってしまうからだ。

参考