再帰関数（自分自身を呼び出す関数）を書く問題を、初級から上級まで12問そろえました。main 関数はあらかじめ書いてあり、あなたが作るのは指定された関数の中身だけです。ループを使わず再帰で書くのが目標です。「採点する」を押すと、本物の gcc でいくつかの入力を試し、出力が正しいかを判定します。
※ 実行と採点では、コードを外部の無料コンパイルサービス Wandbox に送信して gcc で動かします。
int sum_to(int n) を、ループを使わず再帰で作れ。n が 0 のときは 0 を返す。main 関数は用意してある。「実行」で入力を与えて動かす／「採点する」で 4 個のテストを自動で試します
return sum_to(n - 1) + n; です。これだけだと止まらないので、n == 0 のときは 0 を返す終了条件を先に書きます。#include <stdio.h> int sum_to(int n) { if (n == 0) { return 0; } return sum_to(n - 1) + n; } int main(void) { int n; scanf("%d", &n); printf("合計: %d\n", sum_to(n)); return 0; }
long long power(int x, int n) を再帰で作れ。x0 は 1 とする（00 も 1）。main 関数は用意してある。「実行」で入力を与えて動かす／「採点する」で 5 個のテストを自動で試します
n == 0 なら 1 を返し、それ以外は return x * power(x, n - 1); とします。#include <stdio.h> long long power(int x, int n) { if (n == 0) { return 1; } return x * power(x, n - 1); } int main(void) { int x, n; scanf("%d %d", &x, &n); if (x < 0) printf("(%d)^%d = %lld\n", x, n, power(x, n)); else printf("%d^%d = %lld\n", x, n, power(x, n)); return 0; }
long long にしています。x * power(...) では x が long long に変換されてから掛け算されます。int count_digits(int n) を再帰で作れ。0 は 1 桁とする。main 関数は用意してある。「実行」で入力を与えて動かす／「採点する」で 5 個のテストを自動で試します
n < 10）なら 1 を返します。そうでなければ、一の位を捨てた n / 10 の桁数に 1 を足したものが答えです。#include <stdio.h> int count_digits(int n) { if (n < 10) { return 1; } return 1 + count_digits(n / 10); } int main(void) { int n; scanf("%d", &n); printf("桁数: %d\n", count_digits(n)); return 0; }
n == 0 で 0 を返す形にすると、入力が 0 のときに桁数が 0 になってしまいます。どの値で止めるかは、いちばん小さい入力（ここでは 0）で答えが合うかで確かめましょう。int fib(int n) を再帰で作れ（0 ≤ n ≤ 30）。main 関数は用意してある。「実行」で入力を与えて動かす／「採点する」で 5 個のテストを自動で試します
n == 0 なら 0、n == 1 なら 1 を返し、それ以外は return fib(n - 1) + fib(n - 2); です。#include <stdio.h> int fib(int n) { if (n == 0) return 0; if (n == 1) return 1; return fib(n - 1) + fib(n - 2); } int main(void) { int n; scanf("%d", &n); printf("fib(%d) = %d\n", n, fib(n)); return 0; }
fib(1) が fib(-1) を呼んで止まりません。なお、この書き方は同じ計算を何度もくり返すため、n が 1 増えるごとに計算量が約 1.6 倍になります（n=30 で約 270 万回の呼び出し）。s[i] から文字列の終わりまでを逆順に表示する関数 void print_reverse(const char s[], int i) を再帰で作れ（ループは使わない）。main 関数は用意してあり、空白を含まない英数字・記号の文字列（100 文字以内）を読んで print_reverse(s, 0) を呼び、最後に改行する。「実行」で入力を与えて動かす／「採点する」で 5 個のテストを自動で試します
s[i] が終端文字 '\0' なら何もせずに戻ります。そうでなければ、先に print_reverse(s, i + 1) で残りを逆順に表示し、そのあとで s[i] を表示します。#include <stdio.h> void print_reverse(const char s[], int i) { if (s[i] == '\0') { return; } print_reverse(s, i + 1); printf("%c", s[i]); } int main(void) { char s[101]; scanf("%100s", s); print_reverse(s, 0); printf("\n"); return 0; }
printf を再帰呼び出しの前に書くと、そのままの順で表示されます。後ろに書くと、いちばん深い呼び出し（最後の文字）から戻ってくる順に表示されるので逆順になります。void print_binary(int n) を再帰で作れ（ループや配列は使わない）。余分な 0 を先頭に付けないこと。0 は 0 と表示する。main 関数は用意してあり、関数を呼んだあと改行する。「実行」で入力を与えて動かす／「採点する」で 6 個のテストを自動で試します
n % 2、それより上の桁は n / 2 の2進数です。上の桁から表示したいので、n >= 2 なら先に print_binary(n / 2) を呼び、そのあとで n % 2 を表示します。#include <stdio.h> void print_binary(int n) { if (n >= 2) { print_binary(n / 2); } printf("%d", n % 2); } int main(void) { int n; scanf("%d", &n); print_binary(n); printf("\n"); return 0; }
n == 0 なら何もしない」にすると、入力 0 のときに何も表示されません。int array_max(const int a[], int n) を再帰で作れ（ループは使わない）。main 関数は用意してあり、n（1 ≤ n ≤ 100）と n 個の整数（絶対値 10000 以下）を読む。「実行」で入力を与えて動かす／「採点する」で 5 個のテストを自動で試します
n == 1）なら a[0] が最大です。そうでなければ、「先頭 n−1 個の最大値」array_max(a, n - 1) と最後の要素 a[n - 1] の大きい方を返します。#include <stdio.h> int array_max(const int a[], int n) { if (n == 1) { return a[0]; } int m = array_max(a, n - 1); if (a[n - 1] > m) { return a[n - 1]; } return m; } int main(void) { int a[100]; int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } printf("最大値: %d\n", array_max(a, n)); return 0; }
a[n] ではなく a[n - 1] です（a[n] は範囲外）。再帰呼び出しの結果を変数 m に受けておくと、同じ呼び出しを2回書かずに済みます。s[left]〜s[right] の部分が回文（前から読んでも後ろから読んでも同じ）なら 1、そうでなければ 0 を返す関数 int is_palindrome(const char s[], int left, int right) を再帰で作れ。main 関数は用意してあり、空白を含まない英小文字の文字列（1〜100 文字）を読んで、文字列全体について判定する。「実行」で入力を与えて動かす／「採点する」で 6 個のテストを自動で試します
left >= right（残りが 1 文字以下）なら回文なので 1 を返します。両端 s[left] と s[right] が違えば 0。同じなら、内側 (left + 1, right - 1) について同じ判定を再帰で行い、その結果を返します。#include <stdio.h> #include <string.h> int is_palindrome(const char s[], int left, int right) { if (left >= right) { return 1; } if (s[left] != s[right]) { return 0; } return is_palindrome(s, left + 1, right - 1); } int main(void) { char s[101]; scanf("%100s", s); int len = (int)strlen(s); if (is_palindrome(s, 0, len - 1)) { printf("%s は回文です\n", s); } else { printf("%s は回文ではありません\n", s); } return 0; }
is_palindrome(...) を呼ぶだけで return を書き忘れると、内側の判定結果が呼び出し元に伝わりません（その値を使うのは未定義動作です）。終了条件を left == right だけにすると、偶数文字（abba など）で left と right がすれ違い、文字列の範囲外まで読みに行ってしまいます。void hanoi(int n, char from, char to, char via) を作れ（from から to へ、via を経由して n 枚を移す）。1回の移動ごとに「円盤k: X -> Y」と1行表示する。main 関数は用意してあり、n（1 ≤ n ≤ 10）を読んで hanoi(n, 'A', 'C', 'B') を呼ぶ。「実行」で入力を与えて動かす／「採点する」で 5 個のテストを自動で試します
n == 0 なら何もしない、が終了条件です。#include <stdio.h> void hanoi(int n, char from, char to, char via) { if (n == 0) { return; } hanoi(n - 1, from, via, to); printf("円盤%d: %c -> %c\n", n, from, to); hanoi(n - 1, via, to, from); } int main(void) { int n; scanf("%d", &n); hanoi(n, 'A', 'C', 'B'); return 0; }
a[lo]〜a[hi] の範囲から key を探し、見つかればその添字を、なければ −1 を返す関数 int bsearch_rec(const int a[], int lo, int hi, int key) を、二分探索の再帰で作れ。main 関数は用意してあり、n（1 ≤ n ≤ 100）、狭義の昇順（同じ値はない）に並んだ n 個の整数、探す値 key の順に読む。添字は 0 から数える。「実行」で入力を与えて動かす／「採点する」で 6 個のテストを自動で試します
lo > hi（探す範囲が空）なら −1 を返します。真ん中 mid = (lo + hi) / 2 を見て、a[mid] == key なら mid を返し、key の方が小さければ左半分 (lo, mid - 1)、大きければ右半分 (mid + 1, hi) を再帰で探して、その結果を return します。#include <stdio.h> int bsearch_rec(const int a[], int lo, int hi, int key) { if (lo > hi) { return -1; } int mid = (lo + hi) / 2; if (a[mid] == key) { return mid; } else if (key < a[mid]) { return bsearch_rec(a, lo, mid - 1, key); } else { return bsearch_rec(a, mid + 1, hi, key); } } int main(void) { int a[100]; int n, key; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } scanf("%d", &key); int pos = bsearch_rec(a, 0, n - 1, key); if (pos >= 0) { printf("%d は a[%d] にあります\n", key, pos); } else { printf("%d は見つかりません\n", key); } return 0; }
(lo, mid) や (mid, hi) にすると、範囲が縮まらずに同じ呼び出しをくり返して止まらないことがあります。mid はもう調べたので必ず外します。1回ごとに範囲が半分になるので、100 個でも7回ほどの呼び出しで終わります。int comb(int n, int r) を、関係式 nCr = n−1Cr−1 + n−1Cr を使った再帰で作れ（階乗は使わない）。nC0 = nCn = 1 とする。main 関数は用意してあり、n と r（0 ≤ r ≤ n ≤ 20）を読む。「実行」で入力を与えて動かす／「採点する」で 6 個のテストを自動で試します
r == 0 || r == n のとき 1 を返すことです。それ以外は return comb(n - 1, r - 1) + comb(n - 1, r);（パスカルの三角形の「左上と右上の和」）です。#include <stdio.h> int comb(int n, int r) { if (r == 0 || r == n) { return 1; } return comb(n - 1, r - 1) + comb(n - 1, r); } int main(void) { int n, r; scanf("%d %d", &n, &r); printf("%dC%d = %d\n", n, r, comb(n, r)); return 0; }
r == 0 だけにすると、comb(n - 1, r) で r が n より大きくなる呼び出しが生まれ、n が負になっても止まりません。両端（r=0 と r=n）の2つが必要です。階乗を使う方法 n!/(r!(n−r)!) は、途中の階乗が int に入らなくなりやすい（13! で int の範囲を超える）点でも、この再帰の方が安全です。void permute(int perm[], int used[], int depth, int n) を再帰で作ること。perm は作りかけの順列、used[k] は数字 k+1 を使用中なら 1、depth はすでに決めた個数。main 関数は用意してあり、n（1 ≤ n ≤ 5）を読んで permute(perm, used, 0, n) を呼ぶ。「実行」で入力を与えて動かす／「採点する」で 5 個のテストを自動で試します
depth == n なら全部決まったので perm を表示して戻ります。そうでなければ、数字 1〜n のうちまだ使っていないものを小さい順に1つ選び、perm[depth] に入れて used を 1 にし、permute(perm, used, depth + 1, n) を呼びます。戻ってきたら used を 0 に戻します。#include <stdio.h> void permute(int perm[], int used[], int depth, int n) { if (depth == n) { for (int i = 0; i < n; i++) { printf("%d ", perm[i]); } printf("\n"); return; } for (int k = 0; k < n; k++) { if (!used[k]) { used[k] = 1; perm[depth] = k + 1; permute(perm, used, depth + 1, n); used[k] = 0; } } } int main(void) { int perm[5]; int used[5] = {0}; int n; scanf("%d", &n); permute(perm, used, 0, n); return 0; }
used[k] = 0; で「使用中」の印を元に戻すのを忘れると、一度使った数字が二度と選べなくなり、最初の 1 つの順列しか出てきません。配列は呼び出し先と共有されるので、印の付け外しを自分で管理する必要があります。順列の数は n! 個（n=5 で 120 個）です。