再帰関数って面白い

再帰関数

再帰関数とは、関数の中でその関数自身を呼び出している関数のこと
ベースケース、再帰ケースと呼ばれる二つの部分からなる。

ベースケースは関数の処理が終了する際の条件が書かれている
再帰ケースは再びその関数自信を呼び出す部分であり、目的の処理の一部を処理した後に、残った部分を以降の処理に任せていく

例）

factorial

int factorial(int n) {
	if(n > 0){
		return n * factorial(n-1);
	} else {
		return 1;
	}
}

上の例はn!（nの階乗）を再帰的に書いた関数
n!は、「n! = n * (n-1)!」と表現することができ、これをコードにしたものが上の例

n>0の時は、再帰ケースであり、nとfactorial(n-1)を掛けたものを返している。
factorial(n-1)の部分では引数の値が一つ小さくなっており、目的の処理（階乗）がどんどん小さくなっていく

elseの時は、ベースケースであり、この部分があるおかげで無限ループが起こることなくfactorial(0)が実行されたときに新たなfactorialが呼び出されなくなる。

再帰関数では処理がスタックされていく
例えば4の階乗では
factorial(4)が呼び出される
factorial(3)が呼び出される
factorial(2)が呼び出される
factorial(1)が呼び出される
factorial(0)が呼び出される
factorial(0)が1を返す
factorial(1)が1 * 1を返す
factorial(2)が2 * 1を返す
factorial(3)が3 * 2を返す
factorial(4)が4 * 6を返す

このように処理が大きな塊から小さな塊の方へ向かっていき、最小単位に分割された後に、その計算結果を大きな塊に使っていく。

あとがき

表現できることの自由度としては、
再帰関数 > while文 > for文　(右ほど自由度小さい)
となっている