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

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

これを再帰で表すと：

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

C++で書くと：

int sum(int n) {
    if (n == 0) return 0;
    return n + sum(n - 1);
}

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

例：

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

C++で書くと：

int a(int n) {
    if (n == 0) return 0;
    return a(n - 1) + 1;
}

フィボナッチ数列：

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

C++で書くと：

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

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

1. 数字を1からnまで順に表示する
2. 数字をnから1まで逆順に表示する
3. 1からnまでの合計を求める ←　終わってるよ
4. nの階乗を求める( n! )
5. 配列を逆順に出力する（インデックスを使う）
   • {1, 2, 3, 4} → 出力: 4 3 2 1
6. 文字列を逆順に出力する（“abc” → “cba”）
7. 回文判定
   • “abba” → true
   • “abcba” → true

#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;
}