プログラミング 再帰

わりとまじめに再帰を勉強する。

#include <stdio.h>

int fact(int num);

int main(void)
{
	printf( "%d\n", fact( 5 ) );
	return 0;
}

int fact(int num)
{
	if( num <= 1 ){ return 1; }    
	return num * fact(num-1);  
}

/***************************************************************************/

#include <stdio.h>

void rec(int num);

int main(void)
{
	rec( 0 );
	return 0;
}

void   rec(int num)
{
	if( num <= 10 ) 
	{
		rec( num+1 );
		printf( "%d\n", num ); 
	}
}

/*****************************************************************************/

大事なのは、
「再帰の場合、繰り返し使われるのは関数内の実行コードとstatic変数だけ。
自動変数の類（引き数も含む）は関数の呼び出し毎にスタックに積まれて、
上位の関数に戻るまではキープされる。」
ということ。
そして、「プログラムは上から順に実行される」という大前提。
再帰が呼ばれると、再帰呼び出しまでの状態が保存されて、
再帰からかえってくると、保存された状態の続きから実行されるというイメージ。
上記の例だと、rec(0)からrec(11)までいったあと、
rec(10)のprintf関数が実行されて、引数の10が表示、
rec(9)のprintf関数が実行されて、引数の9が表示、
...となる。
factの場合は、
5 * fact(4)
4 * fact(3)
3 * fact(2)
2 * fact(1)
fact(1)
までいったあと、
return num * fact(num-1)が実行される。
だから、
2 * 1 = 2が戻ってきて,
3 * 2 = 6が戻ってきて、
4 * 6 = 24が戻ってきて、
5 * 24 = 120が戻ってくる。
左の被演算子=numの値は引数で、スタックに保存されてキープされている。