[SW将校学校ジャングル]WEEK 01開発ログ-II

さいきかんすう

貴重な関数バー
再帰関数とは、ある関数で自分自身を再呼び出して操作を実行する関数です.すなわち,関数定義内に同名の関数が現れる場合を再帰関数と呼ぶ.再帰関数を使用する場合は、スタックオーバーフローを防止するには、終了条件が必要です.

재귀함수의 기본 구조

int sum(int n) 
{
	# 탈출 조건
	if (1 == n) {
		return 1;
	
	# 자신보다 1만큼 작은 숫자를 분신을 만들어서 계산을 시킨다.
	# 분신이 계산을 마치면 자신의 현재 값을 거기에 더한다.
	} else {
		return sum(n-1) + n;
	}
}

再帰関数の呼び出しと戻し

各関数が呼び出されると、メモリに新しい空間が解放され、毎回全く異なる空間で動作します.ソースコードでは同じ空間のように見えますが、実際に実行されるコードはまったく異なる空間で行われます.
main()関数が最初に再帰関数を実行すると、「再帰関数1」というメモリ領域が生成され、操作時に再帰関数を再実行すると、「再帰関数2」という新しいメモリ領域が生成されます.
このように繰り返すと、同じコードはメモリ空間でしか移動せず、メモリが不足するまで無限に繰り返され、プログラムが終了するため、再帰関数を記述する際に、いつ停止すべきかに条件が必要になります.
上図では、「再帰関数3」は、逃げ条件に遭遇して実行を停止し、前の関数に戻り、残りのコードを実行し続け、前の関数に戻る.
TIP
関数の実行コードはメモリに一度だけ格納されます.これは正しいですが、ローカル変数やパラメータなどは、以前の関数呼び出しとは全く関係なく、まったく異なる空間で新しく作成されます.したがって,呼び出すたびに新しいオブジェクトが生成されると考えられる.
再帰関数の長所と短所
再帰関数の利点

は分かりやすいです.

はプログラミングが簡単です.

変数の使用を減らします.

再帰関数の欠点

時間複雑度比重複文は計算しにくい.

は、重複文よりも大きなオーバーヘッド(重複文よりもメモリ使用量が多く、実行時間が長くなる可能性がある)

を有する.

関数が頻繁に呼び出されるため、StackOverFlowが発生する可能性があります.

終了条件はA側とB側でも明確にしなければならない.無限の繰り返しが起こります

無限ループが発生するとCPUがクラッシュする.(繰り返し文メモリ不足時に自動停止)

再帰関数に関する白文問題Githubリンク
白俊宰の関数問題について