再帰処理

　再帰処理とは、プログラミングにおいて、あるプロシージャの処理内部で再びそのプロシージャ自身を呼び出すような処理を指します。関数等のプロシージャ中で自身を呼び出すことで、類似の処理を繰り返すことが可能となります。再帰処理を行う関数を再帰関数と呼びます。
　実例を見ればわかりやすいですが以下の様な関数です。
ある数nが存在し、1, 2, 3, 4, 5,...nまでの数の和を求めたい場合、以下の関数を用いることで引数にnを指定することで、その数を返してくれます。

int sum(int n)
{
　int m;
　if (n == 0) return 0;
　m = sum(n - 1);　　　//自身を呼び出す。
　return n+m;　　　　//nにそれまでの再帰処理の結果を足す。
}

　例えば、n=10のときは、答えは、1+2+3+4+5+6+7+8+9+10=55となります。引数に10を入れて、引数n=10で計算すると、関数の3行目のm=sum(n-1)と書かれた行で自身が呼び出されていることが分かります。この関数が再帰処理の起点となります。そして引数n=9として計算が始まります。繰り返していけば分かりますが、最終的に引数n=0の時2行目の結果より0が戻り値となり、その値が戻る引数n=1の呼び出しでは、起点の3行目の戻り値は、
n+m = 1 + 0 =1
となります。同様にn=2の時は、先ほどの戻り値1からm=1として
n+m = 2 + 1 =3
となり、n=3の時は、戻り値3からm=3として
n+m = 3 + 3 =6
これを繰り返していくことで答えの55を得られます。
n+m = 4 + 6 =10
n+m = 5 +10 = 15
n+m = 6 + 15 =21
n+m = 7 + 21 = 28
n+m = 8 + 28 = 36
n+m = 9 + 36 = 45
n+m = 10 + 45 = 55