C言語で関数の再帰呼び出しを教えて！
こういった悩みにお答えします．
本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Assembler (x64，ARM)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
こういった私から学べます．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
目次
関数の再帰呼び出し
C言語では，関数の再帰呼び出しが可能です．
関数の再帰呼び出しとは，関数の中で自分自身を呼び出すことです．
再帰呼び出しを利用すると，漸化式等の数列で表される式を簡単に記述できます．
関数の再帰呼び出しを利用するアルゴリズム「ユークリッドの互除法」を知りたいあなたはこちからどうぞ．
関数の再帰呼び出しで階乗の計算
階乗を計算する\(a_n = n!\ (n \geq 0)\)は，以下の漸化式で表すことができます．
\begin{eqnarray*}
a_n =
\begin{cases}
a_0 = 1 & (n = 0) \\
a_n = n * a_{n-1} & (n \geq 1)
\end{cases}
\end{eqnarray*}
上記の漸化式を再帰呼び出しをするfactorial関数で表したコードは以下になります．
このように，漸化式をほぼそのままコードに記述できます．
for文で階乗を計算するfactorial_for関数もありますので，コードを比較してみて下さい．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> unsigned int factorial(unsigned int n) { if (n == 0) { return 1; } return n * factorial(n - 1); } unsigned int factorial_for(unsigned int n) { unsigned int i; unsigned int ret = 1; for (i = 1; i <= n; i++) { ret *= i; } return ret; } int main(void) { unsigned int i; unsigned int n; printf("Please input a non-negative integer: "); scanf("%u", &n); printf("factorial():\n"); for (i = 0; i <= n; i++) { printf("%u! = %u\n", i, factorial(i)); } printf("factorial_for():\n"); for (i = 0; i <= n; i++) { printf("%u! = %u\n", i, factorial_for(i)); } return 0; } |
実行結果は以下になります．
3行目の行末に5を入力したら，factorial関数とfactorial_for関数で0!から5!までの計算結果を表示します．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
$ gcc factorial.c $ a.out Please input a non-negative integer: 5 factorial(): 0! = 1 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 factorial_for(): 0! = 1 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 |
関数の再帰呼び出しで順列の計算
順列の計算式\({}_n \mathrm{P}_r (n \geq r)\)は以下になります．
$${}_n \mathrm{P}_r = n * (n - 1) * (n - 2) * \ldots * (n - r + 1) = \frac{n!}{(n-r)!}$$
再帰呼び出しで順列を計算するpermutation関数のコードは以下になります．
permutation関数は，再帰を利用するとスッキリ書けますね．
for文で順列を計算するpermutation_for関数もありますので，コードを比較してみて下さい．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> unsigned int permutation(unsigned int n, unsigned int r) { if (r == 0) { return 1; } return n * permutation(n - 1, r - 1); } unsigned int factorial_for(unsigned int n) { unsigned int i; unsigned int ret = 1; for (i = 1; i <= n; i++) { ret *= i; } return ret; } unsigned int permutation_for(unsigned int n, unsigned int r) { return factorial_for(n) / factorial_for(n - r); } int main(void) { unsigned int n, r; do { printf("Please input n and r (nPr): "); scanf("%u%u", &n, &r); } while (n < r); printf("permutation(%u, %u) = %u\n", n, r, permutation(n, r)); printf("permutation_for(%u, %u) = %u\n", n, r, permutation_for(n, r)); return 0; } |
実行結果は以下になります．
3行目の行末に5と3を入力したら，\({}_5 \mathrm{P}_3 = 60\)と正しく計算できていることがわかります．
|
1 2 3 4 5 |
$ gcc permutation.c $ a.out Please input n and r (nPr): 5 3 permutation(5, 3) = 60 permutation_for(5, 3) = 60 |
関数の再帰呼び出しで組み合わせの計算
組み合わせの計算式\({}_n \mathrm{C}_r (n \geq r)\)は以下になります．
$${}_n \mathrm{C}_r = {}_{n - 1} \mathrm{C}_r + {}_{n - 1} \mathrm{C}_{r - 1} = \frac{n!}{r!(n-r)!}$$
再帰呼び出しで組み合わせを計算するcombination関数のコードは以下になります．
for文で組み合わせを計算するcombination_for関数もありますので，コードを比較してみて下さい．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> unsigned int combination(unsigned int n, unsigned int r) { if (r == 0 || r == n) { return 1; } else if (r == 1) { return n; } return combination(n - 1, r) + combination(n - 1, r - 1); } unsigned int factorial_for(unsigned int n) { unsigned int i; unsigned int ret = 1; for (i = 1; i <= n; i++) { ret *= i; } return ret; } unsigned int combination_for(unsigned int n, unsigned int r) { return factorial_for(n) / (factorial_for(r) * factorial_for(n - r)); } int main(void) { unsigned int n, r; do { printf("Please input n and r (nCr): "); scanf("%u%u", &n, &r); } while (n < r); printf("combination(%u, %u) = %u\n", n, r, combination(n, r)); printf("combination_for(%u, %u) = %u\n", n, r, combination_for(n, r)); return 0; } |
実行結果は以下になります．
3行目の行末に5と3を入力したら，\({}_5 \mathrm{C}_3 = 10\)と正しく計算できていることがわかります．
|
1 2 3 4 5 |
$ gcc combination.c $ a.out Please input n and r (nCr): 5 3 combination(5, 3) = 10 combination_for(5, 3) = 10 |
関数の再帰呼び出しでフィボナッチ数列の計算
関数の再帰呼び出しでフィボナッチ数列を計算します．
フィボナッチ数列とは，下式で定義される関数のことです．
\begin{eqnarray*}
F_n = \left \{
\begin{array}{l}
F_0 &=& 0 \\
F_1 &=& 1 \\
F_n &=& F_{n-1} + F_{n-2} \ {\rm (n \geq 2)}
\end{array}
\right.
\end{eqnarray*}
再帰呼び出しでフィボナッチ数列を計算するfibonacci関数のコードは以下になります．
for文でフィボナッチ数列を計算するfibonacci_for関数もありますので，コードを比較してみて下さい．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> unsigned int fibonacci(unsigned int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } else { return fibonacci(n - 1) + fibonacci(n - 2); } } unsigned int fibonacci_for(unsigned int n) { unsigned int i, ret, f, f2; if (n == 0) { return 0; } else if (n == 1) { return 1; } else { f = 0; f2 = 1; for (i = 2; i <= n; i++) { ret = f + f2; f = f2; f2 = ret; } return ret; } } int main(void) { unsigned int i; unsigned int n; printf("Please input a non-negative integer: "); scanf("%u", &n); printf("fibonacci():\n"); for (i = 0; i <= n; i++) { printf("F_%u = %u\n", i, fibonacci(i)); } printf("fibonacci_for():\n"); for (i = 0; i <= n; i++) { printf("F_%u = %u\n", i, fibonacci_for(i)); } return 0; } |
実行結果は以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
$ gcc fibonacci.c $ a.out Please input a non-negative integer: 10 fibonacci(): F_0 = 0 F_1 = 1 F_2 = 1 F_3 = 2 F_4 = 3 F_5 = 5 F_6 = 8 F_7 = 13 F_8 = 21 F_9 = 34 F_10 = 55 fibonacci_for(): F_0 = 0 F_1 = 1 F_2 = 1 F_3 = 2 F_4 = 3 F_5 = 5 F_6 = 8 F_7 = 13 F_8 = 21 F_9 = 34 F_10 = 55 |
関数の再帰呼び出しでアッカーマン関数の計算
関数の再帰呼び出しでアッカーマン関数を計算します．
アッカーマン関数とは，下式で定義される関数のことです．
\begin{eqnarray*}
A(m, n) = \left \{
\begin{array}{l}
n + 1 & {\rm (if\ m = 0)} \\
A(m - 1, 1) & {\rm (if\ n = 0)} \\
A(m - 1, A(m, n - 1)) & {\rm otherwise}
\end{array}
\right.
\end{eqnarray*}
再帰呼び出しでアッカーマン関数を計算するackermann関数のコードは以下になります．
アッカーマン関数は原始再帰関数でないμ再帰関数のため，for文の実装は難しいので省略します．（頑張ればできます．）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> unsigned int ackermann(unsigned int m, unsigned int n) { if (m == 0) { return n + 1; } else if (n == 0) { return ackermann(m - 1, 1); } else { return ackermann(m - 1, ackermann(m, n - 1)); } } int main(void) { unsigned int m, n; printf("Please input a non-negative integer: "); scanf("%u%u", &m, &n); printf("ackermann(%u, %u) = %u\n", m, n, ackermann(m, n)); return 0; } |
実行結果は以下になります．
こちらの計算結果と比較してみましょう．
|
1 2 3 4 |
$ gcc ackermann.c $ a.out Please input a non-negative integer: 3 2 ackermann(3, 2) = 29 |
まとめ
C言語の関数の再帰呼び出しを紹介しました．
具体的には，階乗，順列，組み合わせ，フィボナッチ数列，アッカーマン関数を計算しました．
また，for文で実装したコードと比較しました．
再帰呼び出しは難しいですが，使いこなすとスッキリしたコードを書けますので，是非習得しましょう！
順列と組み合わせを全通り表示する方法を知りたいあなたはこちらからどうぞ．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
