===== 再帰呼び出しとは？ =====

再帰（さいき）とは、「**自分自身を使って問題を解く方法**」です。  
C++などでは、関数の中でまた自分自身を呼び出すことを「再帰呼び出し」と言います。

==== 例：1〜nまでの合計 ====

求めたいもの： $1 + 2 + 3 + \dots + n$

これを再帰で表すと：

$$
\text{sum}(n) = n + \text{sum}(n-1)
$$

C++で書くと：

<code cpp>
int sum(int n) {
    if (n == 0) return 0;
    return n + sum(n - 1);
}
</code>

==== 離散数学との関係：漸化式 ====

漸化式とは「前の項を使って次の項を定義する」数式のことです。

例：

$$
a(n) = a(n-1) + 1, \quad a(0) = 0
$$

C++で書くと：

<code cpp>
int a(int n) {
    if (n == 0) return 0;
    return a(n - 1) + 1;
}
</code>

==== フィボナッチ数列も再帰で書ける ====

フィボナッチ数列：

$$
F(0) = 0, \quad F(1) = 1, \quad F(n) = F(n-1) + F(n-2)
$$

C++で書くと：

<code cpp>
int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}
</code>

==== 再帰と漸化式の関係まとめ ====

^ 再帰呼び出し ^ 漸化式 ^
| 関数が自分を呼ぶ | 次の項が前の項で定義される |
| 終了条件が必要（例：$n = 0$） | 初期条件が必要（例：$a(0) = 0$） |
| 問題を小さくして解く | 問題を小さくして表現する |

==== ポイント ====
  * 再帰は「問題を小さくして解く」方法
  * 漸化式と同じような考え方
  * 難しい数列の問題も再帰で表現できる


==== 練習問題z ====
  - 数字を1からnまで順に表示する
  - 数字をnから1まで逆順に表示する
  - 1からnまでの合計を求める ←　終わってるよ
  - nの階乗を求める( n! )
  - 配列を逆順に出力する（インデックスを使う）
    * {1, 2, 3, 4} → 出力: 4 3 2 1
  - 文字列を逆順に出力する（"abc" → "cba"）
  - 回文判定
    * "abba" → true
    * "abcba" → true

<code cpp>

#include <iostream>

//1～nまでの和を求める関数
int sum(int n)
{
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		sum = sum + i;
	}
	return sum;
}

//絶対ダメなやつ
void print()
{
	static long long int n = 0;
	std::cout << n << ": Hello, World!" << std::endl;
	n++;
	print();
}

//再帰方程式を考える
//+-> n = 1 : sum = 1
//+-> n     : sum = sum(n-1) + n
int sum_r(int n)
{
	if (n == 1) 
		return 1;
	else 
		return sum_r(n - 1) + n;
}

//sum_r(5)
//->sum_r(4) + 5
//        ->sum_r(3) + 4 + 5
//                ->sum_r(2) + 3 + 4 + 5
//                        ->sum_r(1) + 2 + 3 + 4 + 5

//①1～nを順に表示する（スペース区切り横並び）
void printUp(int n) {
	if (n == 0) return;       // 終了条件
	printUp(n - 1);           // 先に小さい数を出力
	std::cout << n << " ";
}

//②数字をnから1まで逆順に表示する
void printDown(int n) {
	if (n == 0) return;       // 終了条件
	std::cout << n << " ";    // 先に大きい数を出力
	printDown(n - 1);
}

//③1～nを逆順に表示するは上でやってるから省略

//④階乗を求める
int factorial(int n) {
	if (n == 0 || n == 1) return 1; // 終了条件
	return n * factorial(n - 1);    // 再帰呼び出し
}

//⑤配列を逆順に出力する（インデックスを使う）
void printReverseArray(int arr[], int size) {
	if (size == 0) return;                  // 終了条件
	std::cout << arr[size - 1] << " ";      // 最後の要素から出力
	printReverseArray(arr, size - 1);       // 次は1つ前の要素へ
}
//⑥文字列を逆順に出力する
void printReverseString(const std::string& str, int index) {
	if (index < 0) return;                  // 終了条件
	std::cout << str[index];                 // 現在の文字を出力
	printReverseString(str, index - 1);     // 次は前の文字へ
}

//⑦回文判定
bool isPalindrome(const std::string& str, int left, int right) {
	if (left >= right) return true;          // 終了条件
	if (str[left] != str[right]) return false; // 文字が一致しない場合
	return isPalindrome(str, left + 1, right - 1); // 次の文字へ
}

int main() {

	//int s = sum(5);
	//std::cout << "sum(5) = " << s << std::endl;
	//int sr = sum_r(5);
	printDown(10);
	return 0;
}

</code>