第９講 関数の再帰的使用
第１話 関数の再帰的使用とは?
このサイトは、最初魔方陣の研究から始まりました。
その後様々なページを付け加えることによって、
現在の姿になりました。
魔方陣の研究は、私が県立高校教諭になる前の塾教師時代にさかのぼります。
中学１年生から５次魔方陣の作り方
（魔方陣の法則キーボードのF5を押すと実行されます。
あるいはスライドショー→最初からの順にクリックしても実行されます。）
を聞いて、どうしてこんなに簡単な方法で、
５次魔方陣が出来てしまうのかが不思議で、
謎を解明しようとして始まりました。
謎はすぐに解明できましたが、
県立高校教諭になっても研究は継続し、
パソコンに考えさせて、パソコンに高次魔方陣を自動生成させるという研究になりました。
研究を一気に跳躍させたものが、
魔方陣は関数の再帰的使用で生成可能だというアイデアだったのです。
魔方陣が関数の再帰的使用で生成できるにちがいないという発想は、
運転中に生まれました。
ただ、その当時は今から２５年ぐらい前で、
可能だが当時のパソコンの性能では手に負えない計算量になり、
１個作り出すのに、数十日もかかってしまうかもしれないとも考えました。
ですが、やってみると８次魔方陣あたりでも１０分もかからず生成できました。
（ただ、６次魔方陣については１個生成させるのに３日も要しました。
６次魔方陣だけは、私が特殊種法と呼んだ方法では無理だったからです。）
現在の最速プログラムを使用すれば、２６次魔方陣クラスでも、
１秒で数百の勢いで当時のコンピュータのスペックでも生成できますから、
プログラムの出来不出来が大きくものをいうことがわかります。
できの悪いプログラムなら、現在最速のスパコンをつかっても１０次魔方陣クラス辺りで１個も生成できませんが、
できのよいプログラムなら２５年前のパソコンでもいくらでも生成できます。


私は、関数の再帰的使用を分身の術とも名付けています。
たった１人しかいない自分を１０人にも１００人にも分身させることができるのです。
分身の方法はとっても簡単で、
自分に仕事を依頼するです。

関数の再帰的使用とは、自分で自分を呼び出すことです。
普通仕事は他の関数に依頼しますが、
なんと自分に仕事を依頼できるのです。
具体例を見てみましょう。
コード
#include<stdio.h>
void f(int a);
int main() {
　　f(0);
　　return(0);
}
void f(int a) {
　　if (a > 0)printf("私は分身%dです。\n", a); else printf("私が本物です。\n");
　　if (a + 1 < 10)f(a + 1); //分身の術
}
実行画面
私が本物です。
私は分身1です。
私は分身2です。
私は分身3です。
私は分身4です。
私は分身5です。
私は分身6です。
私は分身7です。
私は分身8です。
私は分身9です。

f(a + 1);が自分に仕事を依頼している部分です。
if (a + 1 < 10)がないと永久ループになってエラーします。
分身は私の記憶によると分身は４７００人辺りが限界だからです。
分身と呼んでいますが、
見かけではなく、分身がちゃんと仕事をしています。
main()に呼び出された最初のf()が本体で、
それ以外はf()の分身です。
分身ですが、れっきとした社員の1人です。
つまり、分身も含めれば社員f()は１０人です。
１人で１０人分の仕事が出来ます。
私の記憶が正しければ、
１人で４７００人分の仕事をさせることさえ可能なのです。

私は、再帰的使用のことを入れ子式人形でも比喩します。
入れ子式人形とは、七福神やロシアのマトリョーシカ人形を思い浮かべてもらえればよいと思います。
ロシアのマトリョーシカ人形は、七福神入れ子人形のまねらしいです。
源流は日本にあるようですね。
人形の中により小型の人形が入っているのが入れ子式人形です。
f()が自分を呼び出したときに、自分の中により小さい自分が入れ子式に発生するのだとイメージすればよいのです。

では
実行画面が
a=0
a=1
a=2
a=3
a=4
a=5
a=6
a=7
a=8
a=9
となるようにコードを改良して下さい。