再帰呼び出し｜つまづきやすいポイントと攻略法 徹底解説！

矢沢 久雄
2026-07-21 更新

この連載は、基本情報技術者試験の受験者を対象としたものです。

毎回1つのテーマにしぼって、多くの受験者がつまづきやすいポイントと攻略法を解説します。

今回のテーマは再帰呼び出しです。

再帰呼び出しの仕組み

再帰呼び出し（recursive call）は、関数の処理の中で同じ関数を呼び出すことで繰り返しを実現するプログラミング技法です。
プログラミングでは、while文やfor文などの構文を使って繰り返しを実現しますが、それとは別に、再帰呼び出しという技法もあるのです。

再帰呼び出しで繰り返しを実現できるのは、不思議なことではありません。関数を呼び出すと、関数の先頭から処理が行われます。
したがって、関数の処理の中で同じ関数を呼び出せば、関数の先頭に戻って処理が繰り返されるのです。

再帰呼び出しの仕組みを説明する定番の例として、引数nの階乗を求めるfact関数があります（factは、factorial＝「階乗」という意味です）。
階乗とは、ある数から1までのすべての整数を掛けた値です。
たとえば、5の階乗は、5×4×3×2×1＝120です。
リスト1に、擬似言語で記述したfact関数の例を示します。
ここで注目してほしいのは、n × fact(n － 1)の部分です。fact関数の中で、fact関数を呼び出しています。これが、再帰呼び出しです。

○整数型：fact(整数型：n)
  if (n ＝ 0)
     return 1
  else
     return n × fact(n － 1)
  endif

fact関数の処理内容は、if文を使った分岐になっています。
数学の約束で、0の階乗は1なので、n ＝ 0という条件が成り立てば、return 1で1を返しています。
そうでない場合は、return n × fact(n － 1)という処理を行っています。
これは、たとえば5の階乗は「5×(4の階乗)」で求められるので、nの階乗は「n×(n－1の階乗)」で求められる、という考えをプログラムで表したものです。

再帰呼び出しの処理の流れ

再帰呼び出しに関する問題を攻略するには、再帰呼び出しの仕組みを理解しておくのはもちろんですが、再帰呼び出しの処理の流れをトレースできるようにしておく必要もあります。そういう問題も出るからです。
先ほどリスト1に示したfact関数を引数5で呼び出したときの処理の流れをトレースしてみましょう。以下の（1）～（12）になります。

fact(5)→fact(4)→fact(3)→fact(2)→fact(1)→fact(0)という順に関数が呼び出されます。
この時点では、まだどの関数も戻り値を返していません。
fact(0)が1という戻り値を返すと、そこからfact(1)が1を返す→fact(2)が2を返す→fact(3)が6を返す→fact(4)が24を返す→fact(5)が120を返す、という順に戻り値が返されます。これが、再帰呼び出しの処理の流れです。

再帰呼び出しに関する問題（1）

再帰呼び出しに関する問題を見てみましょう。
短い問題が多いので、一気に4問を紹介します。

1問目は、階乗を求める関数の穴埋め問題（出典：H28春問07）です。

関数F(n)の機能は、先ほどリスト1で示した関数fact(n)と同様なので、すぐにわかるでしょう。
n ＞ 0のときは、n × F(n － 1)という再帰呼び出しを行います。
したがって、選択肢ウが正解です。

再帰呼び出しに関する問題（2）

2問目は、階乗を求める関数の乗算回数の問題（出典：H24秋問07）です。

問題2（出典：H24秋問07）

n ! の値を，次の関数F(n)によって計算する。乗算の回数を表す式はどれか。

　ア　 n – 1　　　　イ 　n　　　　ウ 　n²　　　　エ　 n !

この問題の関数F(n)の機能も、先ほどリスト1で示した関数fact(n)と同様です。
乗算の回数は、たとえば5の階乗なら5×4×3×2×1の4回なので、nの階乗ならn － 1回だと思うかもしれませんが、正解は選択肢イのn回です。
なぜなら、1の階乗を求めるときに、1×(0の階乗)という再帰呼び出しが行われるからです。
5の階乗を5×4×3×2×1×1という5回の乗算で求めることになるので、nの階乗ならn回の乗算になります。

再帰呼び出しに関する問題（3）

3問目は、掛け算ではなく足し算を使った関数の問題（出典：R01秋問11）です。

関数f(n)の処理内容は、もしもn ≦ 1なら1を返し、そうでないなら再帰呼び出しでn ＋ f(n － 1)を返す、というものです。
f(5)の処理の流れをトレースすると、以下の（1）～（10）になります。f(5)は15を返すので、選択肢ウが正解です。

再帰呼び出しに関する問題（4）

4問目は、掛け算ではなくmod演算を使った関数の問題（出典：H28秋問07）です。

問題4（出典：H28秋問07）

整数 x, y (x > y ≧ 0) に対して，次のように定義された関数 F(x, y) がある。
F(231, 15) の値は幾らか。ここで，x mod y は x を y で割った余りである。

ア 2　　 イ 3 　　 ウ 5　　 エ 7

関数F(x, y)の処理内容は、もしもy ＝ 0ならxを返し、y ＞ 0ならF(y, x mod y)を再帰呼び出しする、というものです。
F(231, 15)の処理の流れをトレースすると、以下の（1）～（5）になります。F(231, 15)は3を返すので、選択肢イが正解です。

今回は、「再帰呼び出し」のポイントと攻略法を解説しました。
このテーマが苦手だった受験者の参考になれば幸いです。

それでは、またお会いしましょう！

再帰呼び出し｜つまづきやすいポイントと攻略法 徹底解説！

update 2026-07-21

モジュール結合度｜つまづきやすいポイントと攻略法 徹底解説！

update 2026-06-10

RAID｜つまづきやすいポイントと攻略法 徹底解説！

update 2026-05-20

MIPS｜つまづきやすいポイントと攻略法 徹底解説！

update 2026-04-20

暗号化｜つまづきやすいポイントと攻略法 徹底解説！

update 2026-03-24

IPアドレス｜つまづきやすいポイントと攻略法 徹底解説！

update 2026-02-24

ネットワークの識別番号｜つまづきやすいポイントと攻略法 徹底解説！

update 2026-01-26

OSI基本参照モデル｜つまづきやすいポイントと攻略法 徹底解説！

update 2025-12-19

関係データベースの正規化｜つまづきやすいポイントと攻略法 徹底解説！

update 2025-11-26

矢沢 久雄

『プログラムはなぜ動くのか』（日経BP）が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”

大手電気メーカーでＰＣの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識０ベースのＩＴエンジニアや一般書店フェアなどの一般的なＰＣユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。

主な著作物

• 「プログラムはなぜ動くのか」（日経BP）
• 「コンピュータはなぜ動くのか」（日経BP）
• 「出るとこだけ! 基本情報技術者」 (翔泳社)
• 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」（翔泳社）
• 「ｉｆとｅｌｓｅの思考術」（ソフトバンククリエイティブ）　など多数