コラッツ予想（角谷予想）

自然数に対して、偶数なら2で割り、奇数なら3倍して1を足す操作を繰り返すと、最終的に1に到達するという予想。再帰関数で操作回数をカウントする。

#include <iostream>
using namespace std;

int countSteps(int num) {
    if (num == 1) return 0;
    if (num % 2 == 0) return 1 + countSteps(num / 2);
    return 1 + countSteps(num * 3 + 1);
}

int main() {
    int input;
    cin >> input;
    cout << countSteps(input) << endl;
    return 0;
}

最大公約数（ユークリッドの互除法）

二つの整数の最大公約数を再帰的に求める手法。

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    int x, y;
    cin >> x >> y;
    cout << gcd(x, y) << endl;
    return 0;
}

数のカウント

自然数nに対して、n/2以下の各数について再帰的にカウントを行う問題。

#include <iostream>
using namespace std;

int totalCount = 0;

void countNumbers(int limit) {
    for (int i = 1; i <= limit / 2; i++) {
        totalCount++;
        countNumbers(i);
    }
}

int main() {
    int n;
    cin >> n;
    totalCount = 1; // 元の数自身
    countNumbers(n);
    cout << totalCount << endl;
    return 0;
}

リンゴの配置問題

m個のリンゴをn個の皿に配置する方法の数を求める。空の皿を許容する場合の分割問題。

#include <iostream>
using namespace std;

int countWays(int apples, int plates) {
    if (apples == 0 || plates == 1) return 1;
    if (plates > apples) return countWays(apples, apples);
    return countWays(apples, plates - 1) + countWays(apples - plates, plates);
}

int main() {
    int m, n;
    cin >> m >> n;
    cout << countWays(m, n) << endl;
    return 0;
}

数字根（ディジタルルート）

整数の各桁の和を求め、一桁になるまで繰り返す処理。

#include <iostream>
using namespace std;

int digitSum(int num) {
    int sum = 0;
    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

void findDigitalRoot(int num) {
    if (num < 10) {
        cout << num << endl;
        return;
    }
    findDigitalRoot(digitSum(num));
}

int main() {
    int n;
    cin >> n;
    findDigitalRoot(n);
    return 0;
}

アッカーマン関数

再帰的に定義される二変数関数で、計算量が非常に急激に増大する特性を持つ。

#include <iostream>
using namespace std;

int ackermann(int m, int n) {
    if (m == 0) return n + 1;
    if (n == 0) return ackermann(m - 1, 1);
    return ackermann(m - 1, ackermann(m, n - 1));
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << ackermann(a, b) << endl;
    return 0;
}

最小公倍数

二つの整数の最小公倍数を再帰的に探索する。

#include <iostream>
using namespace std;

int findLCM(int a, int b, int multiple) {
    if (multiple % a == 0 && multiple % b == 0) return multiple;
    return findLCM(a, b, multiple + 1);
}

int main() {
    int x, y;
    cin >> x >> y;
    int start = (x > y) ? x : y;
    cout << findLCM(x, y, start) << endl;
    return 0;
}

因数分解のパターン数

整数nを因数の積として表す方法の数を再帰的に求める。

#include <iostream>
using namespace std;

int countFactorizations(int num, int minFactor) {
    if (num == 1) return 1;
    int count = 0;
    for (int i = minFactor; i <= num; i++) {
        if (num % i == 0) {
            count += countFactorizations(num / i, i);
        }
    }
    return count;
}

int main() {
    int n;
    cin >> n;
    cout << countFactorizations(n, 2) << endl;
    return 0;
}

エルミート多項式

エルミート多項式は再帰関係を用いて定義される直交多項式の一種。

#include <iostream>
using namespace std;

int hermite(int n, int x) {
    if (n == 0) return 1;
    if (n == 1) return 2 * x;
    return 2 * x * hermite(n - 1, x) - 2 * (n - 1) * hermite(n - 2, x);
}

int main() {
    int degree, value;
    cin >> degree >> value;
    cout << hermite(degree, value) << endl;
    return 0;
}