どうやらタイトルの長さを期待されているようなのでやってみましょう。再帰とは「再帰とは「再帰とは「再帰とは「再帰とは「………」という文のようなものです」という文のようなものです」という文のようなものです」という文のようなものです」という文のようなものです。 ←これが再帰です。

雨のなか学校までデスクトップPC(Linux)とディスプレイを担いできた大馬鹿者、串カツです。
さて、俺が記事を書くからには、なにか頭を使うことを書きたい。
結局、タイトルにある「再帰」について書こうと思います。
結構興味深く、かつ割と身近でおもしろい話題です。
劇とかの展示の列での待ち時間に読むのを推奨。

「再帰」とは

再帰とは、この記事の通りのものです。
…ものですが、プログラムの例しか出てませんね。
ここでは一般人に理解できるように解説を試みます。

さて、まず例を見てみましょう。

• 「広告募集」の広告
• 名作『はてしない物語』の中には、この『はてしない物語』の本それ自体やその中身が登場する
• アンチウイルスソフトをアンチウイルスソフトで検査してみる
• 言葉を説明あるいは定義するのに、言葉を使用します
• 人間は、人間から生まれます(今のところは)
• ネジを作る機械を作るためにはネジが必要である。そのネジを作る別の機械にもまたネジが必要…
• 『“GNU”という名称は、“GNU's Not Unix”(GNUはUnixではない)の再帰頭字語です。』
• nの「階乗」 とは n-1の「階乗」にnを掛けたもの
• 「自然数」に1を足したものもまた「自然数」である
• 「P(n)」が成り立つとき「P(n+1)」もまた成り立つ (数学的帰納法)
• 「集合」を要素にもつ「集合」も定義できる
• 数値ではなく、「関数」を返す「関数」

ちょっと数学っぽいのが混ざってしまいましたが…イメージは把握していただけましたか？
あるものごと、それ自体にそのものが関係してくるもの(別の言いかたをすれば、「一部分」を見ると「全体」が現れているもの)を「再帰的である」と言います(厳密にはちょっと違いますが)。
別の言い方には「自己言及」というのがありますね。こちらの方がメジャーかもしれません。

単純な例として「自然数」で考えましょう。

1. 1は自然数である。
2. 自然数に1を足したものも、また自然数である。
3. 上記のルールに当てはまるもののみが自然数である。

これが「再帰的定義」です。
(厳密にはこれでは足りません。何故なら、1とは何か、足すとは何か、自然数が満たすべき性質(等号やら何やら)とはどのようなものか、などが説明されないからです。詳しくは Peano axioms や Church numeric で調べると良いです。)
「自然数」の定義それ自体の中に「自然数」が出てきましたね。
では、再帰の何が良いのか。それは再帰を使わずに定義してみれば簡単にわかります。

1. 1は自然数である。
2. 2は自然数である。
3. 3は自然数である。
4. 4は自然数である。
5. 5は自然数である。
……

さてどうですか。この「…」は厳密に定義されていませんから、皆さんが思う「自然数」は永遠に定義しきれません。かわいそうな皆さん。
…というようなことになります。「再帰」の有り難みがわかりましたか？

再帰が現れるのは定義のみに限られません。
たとえばフラクタル (画像だけ見ればいいと思います)。
部分を拡大しても、またその全体と同様の構造が現れる。これも再帰です。
あるいは数学的帰納法。「ある命題Aが成り立つ」ことの証明のために、「ある命題Aが成り立つ」ことを仮定します。これも立派な「再帰」です。
あるいは「漸化式」もそうです。数列のある項を決定(定義)するのに、その数列自体の他の項が使われます。
これでわかっていただけましたか。
実はこの記事のタイトルも単に長いだけでなく、「再帰の説明に再帰を利用する」という再帰の構造を持っているのです(こういう言葉遊びは楽しいですね)。

再帰の危うさ

ただし、この「再帰」は真面目に使うなら、正しく使わないと危険です。
たとえば上の『“GNU”という名称は、“GNU's Not Unix”(GNUはUnixではない)の再帰頭字語です。』の例がわかりやすい。
これは言葉遊びなのでわざとですが、結局この文章から「GNU」が何なのかわかりましたか？
『GNU』→『『GNU』's Not Unix』→『『『GNU』's Not Unix』's Not Unix』→『『『『GNU』's Not Unix』's Not Unix』's Not Unix』→…
定義できませんよね。何度も言いますが、これはわざとなので構いません。
しかし、数学やらプログラミングなど、多くの場面ではこれをやられると困ります。
上の再帰に足りなかったものは何なのでしょう。
正しい例を見ればそれがわかります。
「1は自然数である。自然数に1を足したものもまた自然数である。」
「P(1)が成立することが示される。P(k)が成立するときP(k+1)もまた成立する。」
「0!は1。n!はn×(n-1)!」
…おわかりですか？ というかわかってもらわないと困りますが。
先のネジの例だって、世界初のネジは、ネジを使った機械以外によって作られたはずです。
完全な定義や現実の事象には、必ず「再帰」を含まない部分が存在します。
再帰的なものごとにおいて、再帰を含む部分を「再帰部」、再帰を含まない最初の一歩を「基底部」と呼びます。
名前は重要ではありません。再帰は、基底部から始まってスパイラルを描きながら次のステップへ進むのを永遠に繰り返す、ということがわかっていれば良いです。

再帰が何の役に立つのか。今更言うまでもありません。
再帰は物質の構造、論理の構造、様々な法則、あらゆる「繰り返し」を伴う概念・事物に潜むものです。
1を足すことを繰り返す。ネジを作ることを繰り返す。言葉を説明するのに言葉を使う。
私達を覆い尽すような概念や事象の海、その中に「再帰」という共通の構造を見出すことで、人類は更に抽象化という武器を使いこなし、そうして賢く進化してゆくのです。
(うまくキマッターー!!)

ちなみに再帰を使わなくても

「階乗」はΓ関数 (がんまかんすう)を使って、再帰を用いずに定義できます。
漸化式もたまに解いて一般項にできたり、再帰を使ったプログラムもループやCPS変換を使えば再帰を取り除けます(まあループの本質は再帰ですが)。
世の中「これが唯一絶対」なんてものはそうそうないものですし、それは再帰という方法、概念においても同様なのです。

おまけ

外チ氏が言っていた外装のソースコードはちょっとしたC++(一部の特殊な仕様を除いて実質C言語)です。
興味のある方もいらっしゃるかもしれないのでgistに上げときました。垢バレです。まあいいけど。
質問があればそっちのサイトから受け付けますよ。
マイコンはArduino Leonardなので、Arduino用のライブラリというか特殊な関数とか使ってます。コード読んでて必要になったら自分で調べてください。
コードの多くは俺が書いたといっても、仕様は全て外チ氏が決めたものです。
プログラミングって人間語から機械用言語への翻訳のような作業で、実は翻訳前の原作を作る(仕様策定)の方が難しかったりするんですよね。
てなわけで彼が良いと言うのならWTFPLとかにすると思いますが、どうでしょうか。
結構厄介な作業でしたが、signed intへの乗算がオーバーフローするバグに悩んだりとか、関数ポインタを使ってみたりとか、ハードウェア側(端子の番号とかスイッチの方向とか)とのミスマッチに悩まされたり、まあ面白かったです。
一番の収穫は、ArduinoのコードはC++で書けるということの判明と、gentoo Linux上でのマイコン開発のノウハウを手に入れたことですかね。
今度個人のブログのネタにさせていただきます。ごちそうさま。