【初学者向け】疑似言語で理解する再帰とは何か

この記事では、プログラミング初学者に向けて、再帰（さいき）という考え方を、

  • 専門用語を極力使わず
  • 実際のプログラミング言語は使わず
  • 疑似言語のみ

で説明します。

基本情報技術者試験（特に科目B）を学び始めた方や、「再帰がよく分からない」という方を想定しています。

再帰とは何か？

一言で言うと、再帰とは

自分自身を、もう一度呼び出す処理

です。

「同じことを、条件が変わるまで繰り返す」

ただそれだけの考え方です。

再帰のイメージ（まずはコードを見ない）

例えば、次のような仕事を考えてみます。

  • まだ数が残っている → 続ける
  • 数が 0 になった → やめる

この

  • 続ける条件
  • やめる条件

をはっきり分けて考えることが、再帰理解の第一歩です。

再帰に必ず必要なもの

再帰には、必ず次の2つがあります。

  1. 終わる条件（これがないと止まらない）
  2. 自分をもう一度呼ぶ処理

このどちらかが欠けると、再帰は成立しません。

疑似言語で見る、いちばんシンプルな再帰

やりたいこと

数を 3 → 2 → 1 の順に表示したい

疑似言語の例

手続き カウントダウン(n)
    もし n = 0 なら
        戻る            // 終わる条件
    表示(n)
    カウントダウン(n - 1)   // 自分をもう一度呼ぶ
終わり

呼び出し：

カウントダウン(3)

実行の流れ（イメージ）

カウントダウン(3)
  表示 3
  カウントダウン(2)
    表示 2
    カウントダウン(1)
      表示 1
      カウントダウン(0)
        戻る

処理の形は同じで、数だけが小さくなっていく

これが再帰の本質です。

初学者が混乱しやすいポイント

多くの初学者は、次のように考えてしまいます。

  • 全体の流れを一気に理解しようとする
  • 何回呼ばれるかを全部追いかけようとする

しかし、再帰ではそれは不要です。

正しい考え方：1回分だけ考える

再帰では、次の3点だけを見ます。

  • 今の値は何か
  • 終わる条件に当てはまるか
  • まだなら、次を呼ぶか

「この1回で何をするか」

それだけを考えれば十分です。

ループ（for / while）との違い

ループの場合

  • 何回繰り返すかを自分で管理する
  • 回数や条件を意識する必要がある

再帰の場合

  • 「終わるまで同じことをする」と書くだけ
  • 繰り返しの管理を意識しなくてよい

考え方として、再帰の方が自然な場面もあります。

再帰で一番大事な注意点

終わる条件がない再帰は、永遠に続きます。

もし n = 0 なら 戻る

この1行は、必ず必要です。

まとめ

  • 再帰とは 自分自身を呼ぶ処理
  • 必須なのは
    • 終わる条件
    • 自分を呼ぶ処理
  • 再帰は 1回分だけ考えればよい

再帰は難しく見えますが、

やっていることはとても単純です。

「終わるまで、同じことをする」

この感覚をつかめば、再帰は理解できます。

訪問数 3 回, 今日の訪問数 3回

基本情報技術者,情報処理試験

Posted by hidepon