1. はじめに
再帰は、関数型言語のみならず、あらゆるプログラミングパラダイムにおいて極めて重要な概念である。本稿では、数学的帰納法との関連性を踏まえながら、再帰関数の設計手法について体系的解説していく。
2. 再帰と数学的帰納法
2.1 数学的帰納法の原理
数学的帰納法は、自然数に関する命題を証明するための手法である。その原理は以下の2つのステップから構成される。
基本ステップ：nが初期値（通常はn=1）において命題が成立することを証明する。
帰納ステップ：n=kにおいて命題が成立すると仮定し、この仮定を用いてn=k+1においても命題が成立することを証明する。
この2つのステップが証明されれば、命題はすべての自然数について成立することが示される。
具体例として、1からnまでの和の公式を証明する。
1 + 2 + 3 + ... + n = n × (n + 1) / 2
基本ステップ（n=1の場合）：
左辺 = 1、右辺 = 1 × 2 / 2 = 1
帰納ステップ（n=kを仮定）：
1 + 2 + ... + k + (k+1) = k×(k+1)/2 + (k+1)
= (k+1)(k+2)/2
以上より、任意のnについて公式が成立することが証明された。
2.2 プログラミングへの適用
次に、1から100までの和を求めるプログラムを例に、数学的帰納法のプログラミングへの適用を検討する。
#include <stdio.h>
int main() {
int sum = 0;
for (int i = 1; i <= 100; i++) {
sum += i;
}
printf("%d\n", sum);
return 0;
}
このコードの動作を帰納的に分析する。
基本ステップ：i=1のとき、sum=1となり命題が成立する。
帰納ステップ：i-1までの和をf(i-1)で表すと、f(i) = f(i-1) + iが成立する。
この漸化式に基づき、任意のiについて正しい結果が得られることが保証される。
2.3 再帰への橋渡し
再帰とは、関数が自分自身を直接或いは間接的に呼び出すことで問題を解く手法である。再帰的アルゴリズムは、以下の2つの要素から構成される。
- ベースケース：再帰的に呼び出す必要がない基本的なケース
- 再帰ステップ：より小さな部分問題へ分解し、自分自身を呼び出すケース
数学的帰納法と再帰は、いずれも問題を段階的に分解し、小さな部分問題の解から全体の解を構築するという共通思想を持っている。この洞察こそが、再帰的アルゴリズム設計の核心である。
3. 再帰関数の設計原則
効果的な再帰関数を設計する際には、以下の3つの原則に従う。
原則1：関数の意図を明確にする
再帰関数が何をすべきかを明確に定義する。関数の名前と引数から、その役割が我一目で理解できるよう設計する。
原則2：ベースケースを実装する
再帰の终止条件を明確に実装する。ベースケースが不適切だと、無限再帰が発生しスタックオーバーフローを引き起こす。
原則3：帰納ステップを実装する
「より小さな問題」への分解方法を定義し、再帰呼び出しの結果を適切に組み合わせる。
4. 実践的な例題
4.1 桃の問題
問題文
桃を最初に買った個数は不明である。每一天、現在残っている桃の半分を食べ、さらに1個追加で食べる。n日目に桃が1個だけ残る場合、最初に買った桃の個数を求めよ。
制約
2 ≤ n ≤ 30
解法
i日目の残りの桃の個数をf(i)とする。問題の条件から、以下の漸化式が得られる。
- f(1) = 1（最終日の桃の数）
- f(i) = 2 × (f(i-1) + 1)（i > 1）
#include <iostream>
using namespace std;
int computePeaches(int day) {
if (day == 1) {
return 1;
}
return 2 * (computePeaches(day - 1) + 1);
}
int main() {
int n;
cin >> n;
cout << computePeaches(n) << endl;
return 0;
}
4.2 バネ板の問題
問題文
n枚連続したバネ板がある。i番目のバネ板は小球をa[i]だけ前方に弾き上げる。小球が1枚目のバネ板から開始され、バネ板の外に弹出されるまでに必要な弾跳回数を求めよ。
制約
1 ≤ n ≤ 100000、1 ≤ a[i] ≤ 30
解法
当前位置posから弹出までに必要な回数をcount(pos)とする。
- pos ≥ n のとき： уже外に出ているので0回
- pos < n のとき：1 + count(pos + a[pos])
#include <iostream>
#include <vector>
using namespace std;
int countBounces(int pos, const vector<int>& spring, int n) {
if (pos >= n) {
return 0;
}
return 1 + countBounces(pos + spring[pos], spring, n);
}
int main() {
int n;
cin >> n;
vector<int> spring(n);
for (int i = 0; i < n; i++) {
cin >> spring[i];
}
cout << countBounces(0, spring, n) << endl;
return 0;
}
vectorを用いることで、実行時のメモリ割り当てが動的に行われ、配列の静的確保に伴うメモリ消費を最適化できる。
4.3 指数型枚举
問題文
1からnまでの整数から、任意の個数（0個を含む）を選択する組み合わせをすべて列挙せよ。選択された数は昇順で出力し、辞書順でソートせよ。
制約
1 ≤ n ≤ 10
解法
深さ優先探索を用いて、各位置に対して「選択しない」または「どの数を選択するか」を決定していく。
#include <iostream>
using namespace std;
int selected[10];
void outputResult(int depth) {
for (int i = 0; i < depth; i++) {
if (i > 0) cout << " ";
cout << selected[i];
}
cout << endl;
}
void enumerate(int index, int start, int n) {
if (start > n) {
return;
}
for (int num = start; num <= n; num++) {
selected[index] = num;
outputResult(index + 1);
enumerate(index + 1, num + 1, n);
}
}
int main() {
int n;
cin >> n;
enumerate(0, 1, n);
return 0;
}
4.4 組み合わせ型枚举
問題文
1からnまでの整数から、ちょうどm個を選択する組み合わせをすべて列挙せよ。選択された数は昇順で出力し、辞書順でソートせよ。
制約
1 ≤ m ≤ n ≤ 10
解法
指数型枚举的基础上、選択数がmに達した時点で終了する。
#include <iostream>
using namespace std;
int selected[10];
void printResult(int count) {
for (int i = 0; i < count; i++) {
if (i > 0) cout << " ";
cout << selected[i];
}
cout << endl;
}
void combination(int index, int start, int n, int m) {
if (index == m) {
printResult(m);
return;
}
int remaining = m - index - 1;
for (int num = start; num <= n - remaining; num++) {
selected[index] = num;
combination(index + 1, num + 1, n, m);
}
}
int main() {
int n, m;
cin >> n >> m;
combination(0, 1, n, m);
return 0;
}
4.5 順列型枚举
問題文
1からnまでの整数のすべての順列を列挙せよ。辞書順でソートして出力せよ。
制約
1 ≤ n ≤ 8
解法
各位置にまだ使用されていない数を配置していく。使用済みかどうかは訪問フラグで管理する。
#include <iostream>
using namespace std;
int permutation[10];
bool used[10] = {false};
void showResult(int length) {
for (int i = 0; i < length; i++) {
if (i > 0) cout << " ";
cout << permutation[i];
}
cout << endl;
}
void generate(int position, int n) {
if (position == n) {
showResult(n);
return;
}
for (int num = 1; num <= n; num++) {
if (used[num]) continue;
permutation[position] = num;
used[num] = true;
generate(position + 1, n);
used[num] = false;
}
}
int main() {
int n;
cin >> n;
generate(0, n);
return 0;
}
5. まとめ
本稿では、再帰関数の設計手法について学習した。重要なポイントを以下に整理する。
数学的帰納法と再帰は、問題を段階的に分解し、小さな部分問題の解から全体の解を構築するという共通思想を持つ。再帰関数を設計する際は、関数の意図の明確化、ベースケースの適切な実装、そして帰納ステップの実装という3つの原則に従うことが重要である。
實際的な問題では、指数型枚举、組み合わせ型枚举、順列型枚举など、各种各样的探索問題を再帰によって効率的に解くことができる。これらのパターンを習得することで、複雑な問題に対しても再帰的アプローチを適用できるようになる。