再帰関数

今日は二分木探索に向けて、再帰関数のお勉強です。

関数は呼び出されることで、処理を実行します。呼び出される場所は
関数やmainの中ですが、自分自身で自分を呼び出すことで永久ループします。

まぁ合わせ鏡みたいな感じ？
（鏡の中に鏡があって、その鏡の中に鏡があって。。。）

for文やwhile文で下記のように永久ループをさせることができます。
ざっくり言うとコレと同じことを関数でやっちゃおうと言う話

例）



void RecursiveFunc()

{

	printf("RecursiveFunc()\n");

	RecursiveFunc();

}

  • 再帰関数の利点と欠点

利点は「コードを短く、分かりやすくできること」
下のコードはある値の累乗を計算する関数です。
このように一見難しそうな計算も再帰関数を用いれば簡潔に表すことができます。



int mult(int n, int times)

{

	total *= n;

	times--;

	

	if (times > 0)

		return mult(n, times);

	else

		return total;

}
※巻き戻しの話
　再帰処理では基本的にreturnで自分自身を呼び出します。
再帰の終了は戻り値を返します。一度戻り値を返すと
その前の関数(自分自身)に戻り値が返り、
さらにその前の関数に戻り値が返り。。。
と言うように巻き戻しのような処理が発生します。

再帰処理を行う場合はこの巻き戻しに注意して行う必要があります。
（一歩間違えると、永久ループで暴走しますｗ）

一方で、欠点は「オーバーヘッドを伴うこと」
再帰関数では何度も同じ関数が呼び出されます。
呼び出された関数は再帰が終わるまでその状態が保持されます。
そのため、回数の少ない再帰処理では問題ありませんが、
数百回再帰を繰り返す場合は無視できない問題となってしまうのです。


ソートや探索といった処理では繰り返しもしくは巻き戻しの処理を使うことで
より簡潔にコードを記述することが出来ます。

今日は二分木探索の写経までやって寝ることにしよう(-_-)zzz