はじめに
この記事について
「C言語の基礎を学ぼう」をテーマに、自身の知識 + α をアドベントカレンダーにまとめます。
25日間でC言語をマスターしよう - Qiita Advent Calendar 2025 - Qiita
こんな方を対象としています
-
コンピュータがプログラムをどのように動かしているか知りたい／知らない方
-
プログラミングをしてみたい方
-
C言語初心者の方
キーワード
-
再帰関数
-
メモ化
-
動的計画法
説明
再帰関数
関数内で自分自身を呼び出す関数を 再帰関数 といいます。
#include <stdio.h>
void str_to_char_println(char *str);
int main(void) {
char str[100] = "apple";
str_to_char_println(str);
return 0;
}
void str_to_char_println(char *str) {
if (str[0] == '\0') {
return; // 終了条件 : ヌル文字になる
} else {
printf("%c\n", str[0]); // 先頭1文字 + 改行表示
str_to_char_println(str + 1); // 次の文字以降を渡す
return;
}
}
a
p
p
l
e
上記例の動作はこんな感じです。
- 文字列の先頭1文字分の処理をする。
- 次の文字以降の文字列を関数に渡す。
- 上記処理をヌル文字になるまで繰り返す。
再帰関数には重要な特徴があります。
- 終了条件がある
- 問題（引数、処理の対象）を小さくしていく
終了条件が無いと無限ループとなってしまいます。
また、処理の対象を小さくしない場合、いつまでも終了条件に到達しないため、これも無限ループとなってしまいます。
再帰関数は繰り返し処理によく似ています。
for文などで実装するにはどうすべきかを考えてから再帰関数にするのもよいですね。
練習
1. フィボナッチ数列（for）
フィボナッチ数列の第n項を表示してみよう。
まずはfor文で実装しよう。
n: 10
34
ポイント
フィボナッチ数列は、1つ前の項と2つ前の項の和 がその項の値となります。
第1項は 0 、第2項は 1 です。
解答例
#include <stdio.h>
int main(void) {
int i, n = 10;
int k; // 現時点の結果を格納
int b = 1; // 1つ前の項
int bb = 0; // 2つ前の項
printf("n: %d\n", n);
for (i = 3; i <= n; i++) {
k = bb + b;
bb = b; // 次の準備
b = k; // 次の準備
}
printf("%d\n", k);
return 0;
}
n: 10
34
2. フィボナッチ数列（再帰関数）
フィボナッチ数列の第n項を表示してみよう。
再帰関数で実装しよう。
n: 10
34
ポイント
終了条件、および、次の呼び出しをどうすべきか考えましょう。
例えば、10番目の表示には9番目の値と8番目の値が必要です。
解答例
#include <stdio.h>
int fibo(int n);
int main(void) {
int n = 10;
printf("n: %d\n", n);
printf("%d", fibo(n));
return 0;
}
int fibo(int n) {
if (n == 1) {
return 0;
} else if (n == 2) {
return 1;
} else {
return fibo(n-2) + fibo(n-1);
}
}
n: 10
34
3. フィボナッチ数列（動的計画法）
ここで、for文と再帰関数のそれぞれについて、繰り返し回数を計測してみます。
#include <stdio.h>
int fibo_answer_1(int n);
int fibo_answer_2(int n);
// 繰り返し回数を計測するグローバル変数
int count1 = 0;
int count2 = 0;
int main(void) {
int n = 10;
fibo_answer_1(n);
fibo_answer_2(n);
printf("for文: %d 再帰: %d", count1, count2);
return 0;
}
int fibo_answer_1(int n) {
int i, k, bb = 0, b = 1;
for (i = 3; i <= n; i++) {
count1++; // 計測
k = bb + b;
bb = b;
b = k;
}
return k;
}
int fibo_answer_2(int n) {
count2++; // 計測
if (n == 1) {
return 0;
} else if (n == 2) {
return 1;
} else {
return fibo_answer_2(n-2) + fibo_answer_2(n-1);
}
}
for文: 8 再帰: 109
現在の再帰関数はパフォーマンスが非常に悪いことがわかります。
これは、同じ計算を何度もしていることが原因です。
例えば第10項の計算のために第9項と第8項(A)が必要です。
次に、第9項の計算のために第8項(B)と第7項が必要です。
このときAとBは同じ値ですが、それぞれ計算されてしまうのです。
これを防ぐために メモ化 をします。
1度計算した値を格納しておく配列を用意し、すでに計算されている場合はその値を使用するようにします。
プログラムを実装してみましょう。
ポイント
グローバル変数 int memo[100] を定義しましょう。
第3項以降について、配列を-1で初期化し、-1が格納されている箇所は未計算と判断します。
未計算の場合は、計算のために再帰関数を呼び出し、同時に結果をメモ化します。
計算済みの場合は、メモしておいた値を使用しましょう。
解答例
#include <stdio.h>
int memo[100];
int count = 0;
int fibo(int n);
int main(void) {
int n = 10, i;
// メモ初期化
memo[0] = -1;
memo[1] = 0;
memo[2] = 1;
for (i = 3; i < 100; i++) {
memo[i] = -1;
}
printf("n: %d\n", n);
printf("%d\n", fibo(n));
printf("呼び出し回数: %d", count);
return 0;
}
int fibo(int n) {
count++; // 計測
if (memo[n] == -1) {
// 未計算
memo[n] = fibo(n-2) + fibo(n-1);
return memo[n];
} else {
// 計算済み
return memo[n];
}
}
n: 10
34
呼び出し回数: 17
呼び出し回数がぐっと減りましたね。
大きな問題を小さな問題に変換し、メモ化する再帰関数で解く手法を 動的計画法 といいます。
フィボナッチ数列のような単純な問題であればfor文のほうが高速ですが、動的計画法でなければ解けない複雑な問題も存在します。
おわりに
動的計画法は強力ですが、再帰関数も含めて理解が難しいところもあると思います。
こんな手法があるということだけでも覚えておくとよいですね。
参考文献
↓↓↓ はじめてプログラミングを学んだときに読んだ本です ↓↓↓
詳細（プログラミング入門 C言語）｜プログラミング｜情報｜実教出版