プログラミング 再帰
わりとまじめに再帰を勉強する。
#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の値は引数で、スタックに保存されてキープされている。