C LANGUAGE TECHNOLOGY

【C言語】関数の再帰呼び出し【階乗,順列,組み合わせ,フィボナッチ数列,アッカーマン関数】

悩んでいる人

C言語で関数の再帰呼び出しを教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity/Vyper,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

関数の再帰呼び出し

C言語では,関数の再帰呼び出しが可能です.

関数の再帰呼び出しとは,関数の中で自分自身を呼び出すことです.

再帰呼び出しを利用すると,漸化式等の数列で表される式を簡単に記述できます.

関数の再帰呼び出しを利用するアルゴリズム「ユークリッドの互除法」を知りたいあなたはこちからどうぞ.

C言語 ユークリッドの互除法
【C言語】ユークリッドの互除法で最大公約数と最小公倍数の計算【オイラーのトーシェント関数】

こういった悩みにお答えします. こういった私から学べます. 目次1 ユークリッドの互除法2 C言語のユークリッドの互除法で最大公約数と最小公倍数の計算3 拡張ユークリッドの互除法4 拡張ユークリッドの ...

続きを見る

関数の再帰呼び出しで階乗の計算

階乗を計算する\(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関数もありますので,コードを比較してみて下さい.

実行結果は以下になります.

3行目の行末に5を入力したら,factorial関数とfactorial_for関数で0!から5!までの計算結果を表示します.

関数の再帰呼び出しで順列の計算

順列の計算式\({}_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関数もありますので,コードを比較してみて下さい.

実行結果は以下になります.

3行目の行末に5と3を入力したら,\({}_5 \mathrm{P}_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関数もありますので,コードを比較してみて下さい.

実行結果は以下になります.

3行目の行末に5と3を入力したら,\({}_5 \mathrm{C}_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関数もありますので,コードを比較してみて下さい.

実行結果は以下になります.

関数の再帰呼び出しでアッカーマン関数の計算

関数の再帰呼び出しでアッカーマン関数を計算します.

アッカーマン関数とは,下式で定義される関数のことです.

\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文の実装は難しいので省略します.(頑張ればできます.)

実行結果は以下になります.

こちらの計算結果と比較してみましょう.

まとめ

C言語の関数の再帰呼び出しを紹介しました.

具体的には,階乗,順列,組み合わせ,フィボナッチ数列,アッカーマン関数を計算しました.

また,for文で実装したコードと比較しました.

再帰呼び出しは難しいですが,使いこなすとスッキリしたコードを書けますので,是非習得しましょう!

順列と組み合わせを全通り表示する方法を知りたいあなたはこちらからどうぞ.

C言語 順列と組み合わせ 全通り表示
【C/C++言語】順列と組み合わせを全通り表示

こういった悩みにお答えします. こういった私から学べます. C/C++言語で順列と組み合わせを全通り表示する方法を紹介します. 順列と組み合わせの個数を計算する方法を知りたいあなたは,関数の再帰呼び出 ...

続きを見る

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , , , , , , , ,