🖥️
【C言語入門の次】第01回再帰関数

2025/06/06に公開
https://youtu.be/12LMMQ3727g


\textcolor{pink}{四国めたん: }教師役ですわ


\textcolor{lime}{ずんだもん: }生徒役なのだ
\footnotesize \textcolor{pink}{四国めたん:} こんにちは。四国めたんです
\footnotesize \textcolor{lime}{ずんだもん:} ずんだもんなのだ。こんにちはなのだ
\footnotesize \textcolor{pink}{四国めたん:} 今回からC言語の入門の次のステップとしてアルゴリズムを中心にお話ししますわ
\footnotesize \textcolor{lime}{ずんだもん:} プログラミングに少し慣れてきたので丁度いいのだ
\footnotesize \textcolor{pink}{四国めたん:} はい、今回は再帰関数についてお話ししますわ
\footnotesize \textcolor{lime}{ずんだもん:} よろしくなのだ

 再帰関数はこんな感じです\footnotesize \textcolor{lime}{ずんだもん:} ところで 再帰関数 とは何なのだ？
\footnotesize \textcolor{pink}{四国めたん:}  再帰関数 とは、関数内で自身の関数を呼び出すようにした関数のことですわ
\footnotesize \textcolor{lime}{ずんだもん:} イメージがつかめないのだ
\footnotesize \textcolor{pink}{四国めたん:} おおまかな形はこのようになりますわね
戻り値 関数名(引数の型 引数名, ...) {
    :
    :
  関数名(実引数, ...);
    :
  return 戻り値;
}
\footnotesize \textcolor{lime}{ずんだもん:} 関数内で自身の関数を呼び出しているのだ
\footnotesize \textcolor{pink}{四国めたん:} はい、自身の関数を再帰的に呼び出すので 再帰関数 なのですわ
\footnotesize \textcolor{lime}{ずんだもん:} でも、このまま関数を呼び出してしまうと、永久に関数を呼び出し続けてしまうのだ
\footnotesize \textcolor{pink}{四国めたん:} はい、最終的にはメモリ不足となって破綻しますわね
\footnotesize \textcolor{lime}{ずんだもん:} どうするのだ？
\footnotesize \textcolor{pink}{四国めたん:} そこで、 再帰関数 では必ずストッパーとなる機能を盛り込みますわ
\footnotesize \textcolor{lime}{ずんだもん:} ストッパー？
\footnotesize \textcolor{pink}{四国めたん:} はい、こんな感じですわ
戻り値 関数名(引数の型 引数名, ...) {
    :
  if (ストップ条件) {    // (1)
      :
    return 最終の戻り値;
  } else {
      :
    関数名(実引数, ...);
      :
    return 戻り値;
  }
}
\footnotesize \textcolor{pink}{四国めたん:} (1)でストップ条件に合致すれば、自身の関数を呼び出さずに、そのまま戻るようにしますわ
\footnotesize \textcolor{lime}{ずんだもん:} なるほどなのだ
\footnotesize \textcolor{pink}{四国めたん:} なお、ストップ条件は、関数を呼び出した回数や引数の値などを使うのが一般的ですわ
\footnotesize \textcolor{lime}{ずんだもん:} りょうかいなのだ

 階乗計算をやってみよう\footnotesize \textcolor{pink}{四国めたん:} とりあえず 再帰関数 の概要を見てみましたが、いかがでしたか？
\footnotesize \textcolor{lime}{ずんだもん:} う～ん、これだけではあまりピンと来ないのだ
\footnotesize \textcolor{pink}{四国めたん:} それでは具体的な例として、よく使われる 階乗計算 を取り上げてみましょう
\footnotesize \textcolor{lime}{ずんだもん:} うむ、 階乗計算 なら知っているのだ
\footnotesize \textcolor{lime}{ずんだもん:} 計算式はこんな感じだったのだ

n! = n \times (n - 1) \times (n - 2) \times \dotsb \times 1
\footnotesize \textcolor{pink}{四国めたん:} はい、これを修正すると、このようになりますわ

n! = n \times (n - 1)!
\footnotesize \textcolor{lime}{ずんだもん:} つまり、(n - 1)の階乗にnを掛けることでnの階乗を得られると云うことなのだ
\footnotesize \textcolor{pink}{四国めたん:} はい、これを 再帰関数 として実装してみましょう
#include <conio.h>
#include <stdio.h>

int factional(int n) {
  int rc = -1;
  if (n > 0) {
    rc = n * factional(n - 1);
  } else if (n == 0) {
    rc = 1;
  }
  return rc;
}

int main(int argc, char* argv[]) {
  int c = 0;
  do {
    printf("数値を入力して下さい(ESC:終了) ");
    c = _getch();
    if ((c <= '9') && (c >= '0')) {
      int n = c - '0';
      int f = factional(n);
      printf("%dの階乗は%dです。\n", n, f);
    }
  } while (c != 27);  // ESCの入力
  return 0;
}

 階乗計算の関数\footnotesize \textcolor{pink}{四国めたん:} まず、階乗計算の関数factionalですわ
\footnotesize \textcolor{lime}{ずんだもん:} 引数"n"に整数を指定すると、n!を返す関数なのだ
\footnotesize \textcolor{pink}{四国めたん:} まず、最初に戻り値"rc"を-1、つまり計算の失敗を示す値で初期化していますわ
\footnotesize \textcolor{lime}{ずんだもん:} ふむ
\footnotesize \textcolor{pink}{四国めたん:} 次に引数が0を超える整数の場合は、n \times (n - 1)! を計算して戻り値"rc"としますわ
\footnotesize \textcolor{lime}{ずんだもん:} なるほどなのだ
\footnotesize \textcolor{pink}{四国めたん:} (n - 1)! については、自身の関数factionalを呼び出すことで取得していますわ
\footnotesize \textcolor{lime}{ずんだもん:} このときの引数は"n - 1"としているのだ
\footnotesize \textcolor{pink}{四国めたん:} 次に引数が0の場合は、戻り値"rc"として0!、つまり1を返しますわ
\footnotesize \textcolor{lime}{ずんだもん:} これが 再帰関数 "factional"の終了条件となるのだ
\footnotesize \textcolor{pink}{四国めたん:} もし引数が負の整数の場合には、戻り値"rc"は-1のままなので、計算失敗としますわ
\footnotesize \textcolor{lime}{ずんだもん:} りょうかいなのだ

 メイン関数\footnotesize \textcolor{lime}{ずんだもん:} つぎはメイン関数なのだ
\footnotesize \textcolor{pink}{四国めたん:} はい、メイン関数ではdo～whileループを使用しますわ
\footnotesize \textcolor{lime}{ずんだもん:} うむ
\footnotesize \textcolor{pink}{四国めたん:} 最初にキーボードから 数値の入力 を促すと共に、_getch()関数で1文字の入力を待ちますわ
\footnotesize \textcolor{lime}{ずんだもん:}  階乗計算 に使う数値を入力するのだ
\footnotesize \textcolor{pink}{四国めたん:} キーボードからの入力は、最初に宣言している変数"c"に代入しますわ
\footnotesize \textcolor{lime}{ずんだもん:} 文字は数値と同じなのでint型の変数に代入できるのだ
\footnotesize \textcolor{pink}{四国めたん:} そしてif文でキーボードからの入力が0～9の数値なのを確認しますわ
\footnotesize \textcolor{lime}{ずんだもん:} 数値であるかどうかは大事なのだ
\footnotesize \textcolor{pink}{四国めたん:} はい、確認ができたらc -  **0** で入力された 0 ～ 9 の文字を整数の0～9に変更しますわ
\footnotesize \textcolor{lime}{ずんだもん:} まぁ、一般的に使われるテクニックなので、覚えておくとべんりなのだ
\footnotesize \textcolor{pink}{四国めたん:} 次に、変換された0～9の整数を引数にfactional関数を呼び出して 階乗計算 をおこないますわ
\footnotesize \textcolor{lime}{ずんだもん:} 得られた値はコンソールに出力するのだ
\footnotesize \textcolor{pink}{四国めたん:} なお、whileの条件式でキーボードの入力が\fcolorbox{blue}{lightgray}{ESC}かどうかをチェックしていますわ
\footnotesize \textcolor{lime}{ずんだもん:} なぜ27と比較しているのだ？
\footnotesize \textcolor{pink}{四国めたん:} 27と比較しているのは、ASCIIコード表で\fcolorbox{blue}{lightgray}{ESC}に相当する整数値が27だからですわ
\footnotesize \textcolor{lime}{ずんだもん:} りょうかいなのだ
\footnotesize \textcolor{pink}{四国めたん:} キーボードの入力が\fcolorbox{blue}{lightgray}{ESC}ならwhileループを抜け、プログラムを終了しますわ
\footnotesize \textcolor{lime}{ずんだもん:} ふむ
\footnotesize \textcolor{pink}{四国めたん:} それでは実行してキーボードから0～9までの数字を入力した後、\fcolorbox{blue}{lightgray}{ESC}で終了しますわ

 再帰関数はループにできます\footnotesize \textcolor{pink}{四国めたん:} ところで 再帰関数 については、whileループやforループで同じ結果を得ることができますわ
\footnotesize \textcolor{lime}{ずんだもん:} そうなのか？
\footnotesize \textcolor{pink}{四国めたん:} 例えば階乗計算であれば、このようにできますわ
int factional(int n) {
  int rc = 1;
  if (n > 0) {
    for (int i = n; i > 0; i--) {
      rc *= i;
    }
  } else if (n < 0) {
    rc = -1;
  }
  return rc;
}
\footnotesize \textcolor{pink}{四国めたん:} まず、戻り値"rc"の初期値は、0!である1としますわ
\footnotesize \textcolor{lime}{ずんだもん:} ふむふむ
\footnotesize \textcolor{pink}{四国めたん:} もし引数が正の整数の場合はforループでn～1までを戻り値"rc"に掛けますわ
\footnotesize \textcolor{lime}{ずんだもん:} あぁ、 階乗計算 の n! = n \times (n - 1) \times (n - 2) \times \dotsb \times 1 そのものなのだ
\footnotesize \textcolor{pink}{四国めたん:} はい、次に引数が負の整数の場合は、戻り値"rc"を-1にしますわ
\footnotesize \textcolor{lime}{ずんだもん:} エラー処理なのだ
\footnotesize \textcolor{pink}{四国めたん:} というわけで、変換の方法は様々ですが、必ず 再帰関数 をwhileループやforループに変えることができますわ
\footnotesize \textcolor{lime}{ずんだもん:} なるほどなのだ
\footnotesize \textcolor{pink}{四国めたん:} ちなみに 再帰関数 を使うメリットは、プログラムが簡潔になることですわ
\footnotesize \textcolor{lime}{ずんだもん:} そうなのか？
\footnotesize \textcolor{pink}{四国めたん:} 逆に、速度は 再帰関数 よりもwhileループやforループの方が速い場合が殆どですわね
\footnotesize \textcolor{lime}{ずんだもん:} りょうかいなのだ
\footnotesize \textcolor{pink}{四国めたん:} また、呼び出す回数にもよりますが、メモリ使用量も通常は 再帰関数 の方が多くなりますわ
\footnotesize \textcolor{lime}{ずんだもん:} なるほどなのだ
\footnotesize \textcolor{pink}{四国めたん:} なので、実用的なプログラムを作る場合には、 再帰関数 よりもwhileループやforループを使うことをお勧めしますわ
\footnotesize \textcolor{lime}{ずんだもん:} わかったのだ
\footnotesize \textcolor{pink}{四国めたん:} 反対に、アルゴリズムを説明する場合には 再帰関数 をよく使いますわね
\footnotesize \textcolor{lime}{ずんだもん:} うむ
AIってすごいですね再帰関数 をwhileループやforループの関数に変換するのは結構大変な場合があります
階乗計算 程度であれば問題ないのですが...
ただ、最近ではAIにお願いすれば、あっという間に書き換えてくれるので、大変便利です
別に有料の凄いAIで無くても問題ないです
Windowsに付属の Copilot でも、 再帰関数 をコピペして、「再帰を使わない関数にして」とお願いすれば、直ぐに回答してくれます
もちろんチェックは必要ですが、便利な時代になったものです
おまけ tgamma実は階乗計算は 再帰関数 やループを使わなくても 標準Cライブラリ を使って簡単に計算できます。
#include <math.h>

int factional(int n) {
  int rc = 1;
  if (n > 0) {
    rc = tgamma(n + 1);
  } else if (n < 0) {
    rc = -1;
  }
  return rc;
}
ガンマ関数を使うと、階乗計算はこのようにして計算できます

n! = \varGamma(n + 1)
ただしnは自然数(正の整数)に限られます
なのでfactional関数内では引数nが正の整数の場合のみ、階乗を計算しています
tgammaは"math.h"に含まれた関数で、ガンマ関数の計算をおこないます
ちなみにtgammaは、引数も戻り値もdouble型ですが、0～9の範囲では整数で使用しても問題なく使えます
ワーニングは出てしまいますが...

 まとめ\footnotesize \textcolor{pink}{四国めたん:} お疲れさまでした
\footnotesize \textcolor{lime}{ずんだもん:} おつかれさまなのだ
\footnotesize \textcolor{pink}{四国めたん:} 以上で 再帰関数 を終了しますわ
再帰関数はこんな感じです

階乗計算をやってみよう

階乗計算の関数

メイン関数

再帰関数はループにできます

まとめ

Discussion
