【擬似言語⑩】階乗 | ループと再帰関数（基本情報技術者, 科目B, アルゴリズム）

このNoteでは、「階乗」を題材に再帰関数/再帰呼出しを学習します。

「再帰呼出し」は、自分自身を関数として呼び出す”合わせ鏡”みたいな処理。ミスると無限ループになる要注意なテクニックです。

科目Aでも出てますし、科目Bでは「階乗」の他に、2分木/クイックソートでも出題されました。

テキストの基礎を生かして、プログラム的な考察/工夫を学んでいきます。基礎と実用にギャップを感じる方のために作りました。
＞【FEB】擬似言語の教科書Note

ぜひ一緒に学習を進めていきましょう！

このNoteは、私がIT専門学校で授業したことを基に作成しています。IT専門学校でFEは第一目標として、カリキュラムが構築されています。何も知らずに入学しても、1年生10月にはFE合格していきますよ。実績ある教育ノウハウを詰め込んだので、少しでも信頼して頂けたら嬉しいです。

＞全Noteへのリンク（FE節）
※科目Aのテーマ別/科目B/旧FE午後など沢山作りました！

数式通りに擬似言語

「f(3)=3×2×1」。forループで「iを3から1まで1ずつ減らす」方式を考えます。数式を擬似言語のパーツ（if, forなど）で素直に実現。

○整数型: calcFactorial(整数型: n)
  整数型: i, result
  result ← 1  
  for (i を n から 1 まで 1 ずつ減らす)
    result ← result × i
  endfor
  return result

for文は割と「iを1から」や「1ずつ増やす」が多かったしシンプル/分かり易いですが。「減らす」でも構いません。

･･･と云いつつ。

「f(3)=3×2×1=1×2×3」と考えると、いつもの「iを1から1ずつ増やす」でいいじゃん（草）。

○整数型: calcFactorial(整数型: n)
  整数型: i, result
  result ← 1  
  for (i を 1 から n まで 1 ずつ増やす)
    result ← result × i
  endfor
  return result

どちらを使うかは好みですかね。私は「いつも、iを1から～1ずつ増やす、で固定。個数カウントもできるし」と書きましたが、今回は数式準拠（1ずつ減らす）を採用します（ダブスタ💦
＞【擬似言語④】平均 | 個数カウントのNote

「0!」を視野に入れる→入ってた

「0!」を考えとかないと計算で困ります。

順列Pの公式の分母。(n-r)!があり、0!=0だと計算できないんです。1/0はプログラムでは「エラー（0除算）」、数学的には「∞」になります。

0!=1です。以下のように規則性から定義します。

下図の緑「×1」が隠れている、と考えます。

数学的にも「0!=1」と定義されてるので、f(0)に対応すべきです（wikipedia）。

実はちゃんと「0!=1」となるように組んでました。

○整数型: calcFactorial(整数型: n←0)
  整数型: i, result
  result ← 1  
  for (i を n=0 から 1 まで 1 ずつ減らす)
    result ← result × i
  endfor
  return result

for(iを0から1まで1ずつ減らす)なので、ループは0回（実行しない）。でもfor前の初期化でresult←1してるので、return 1。
※ひょっとしたら、意図せぬバグになるかもですがご容赦。

for文（1ずつ増やす）版でも同じ。

○整数型: calcFactorial(整数型: n←0)
  整数型: i, result
  result ← 1  
  for (i を 1 から n=0 まで 1 ずつ増やす)
    result ← result × i
  endfor
  return result

n=0の時。ループ実行しないけど、ループ前にresult←1。

プログラムならでは 再帰呼出し/再帰関数

さて今回の新しい学び/応用。「再帰呼出し/再帰関数」を使ってみます。

再帰呼出しは、「自分自身を再度呼出す」こと。科目Aでも出題されてましたね。
＞【FE計算①】再帰関数のNote
＞【AP計算⑲】再帰関数のNote

例えば、f(x)が「x>0の時はf(x-1)を呼び、返り値がきたら、xを返す」「x=0の時は1を返して終了」という条件分岐付きの関数。

下図。
f(3)でf(2)を呼び。
f(2)はf(1)を呼び。
f(1)はf(0)を呼び。
f(0)は1を返して関数終了。
f(0)を呼び出したf(1)に戻って、1×1=1を返してf(1)終了。
f(1)を呼び出したf(2)に戻って、2×1=2を返してf(2)終了。
f(2)を呼び出したf(3)に戻ったら、3×2=6を返してf(3)終了。
全体が終了。

返り値を掛け算すれば「3×2×1×1」と階乗が計算できました。

「×1」が1回多いですが掛け算なので問題なし。

前節でも緑「×1」がある、って解釈でしたね。

再帰関数の擬似言語

では「階乗」の擬似言語を作ります。

再度掲載。f(x)が「x>0の時はf(x-1)を呼び、返り値がきたら、xを返す」「x=0の時は1を返して終了」という条件分岐付きの関数。

○整数型: calcFactorialRecur(整数型: n)
  
  / A. 再帰の終了条件 */
  if (n == 0)
    return 1
  endif
  
  / B. 自分自身を呼び出す */
  return n × calcFactorialRecurs(n - 1)

簡単だったので引数のエラー検知をしますか。f(x)のxは0以上の整数（x≧0）です。数学的に。

○整数型: calcFactorialRecur(整数型: n)
  / 異常値チェック：マイナスならエラーを返す */
  if (n < 0)
    return -1  / エラー時の返り値 */
  endif

  / A. 再帰の終了条件 */
  if (n == 0)
    return 1
  endif
  
  / B. 自分自身を呼び出す */
  return n × calcFactorialRecurs(n - 1)

n<0の時のエラー処理を追加しただけです。引数チェックは関数の最初にやります。＞【擬似言語②】ジャンケンのNote（引数検査）

階乗の応用 | 順列Pと組合わせC

科目Aに出まくってた計算問題なので、科目Bにも出してきたんですね。
＞【FE計算⑧】パターン数のNote
＞【FE計算⑨】確率は幅広く使えるNote
＞【FE計算①】再帰関数のNote
＞【AP計算③】組合せCのNote
＞【AP計算④】確率と期待値のNote
＞【AP計算⑤】期待値のNote
＞【AP計算⑲】再帰関数のNote

例えば組合せの公式。分子と分母に階乗があります。

$$_nC_r=\frac{n!}{r!\times(n-r)!}\\$$

まとめ

お疲れ様でした！

再帰呼び出しは、無限ループになったり、間違った計算をするバグに陥りやすいです。私もプログラムでは滅多に使いません。

公開問題でもトレースはしんどいです。でも正解できるようになってくださいね。変数トレースなど細かいのではなく、関数呼び出しと少し大きい視点（マクロ）です。
＞【FEB】サンプル1問07のNote（階乗）
＞【FEB】サンプル1問09のNote（2分木）
＞【FEB】令和05年問03のNote（クイックソート）
＞【FEB】サンプル1問04のNote（最大公約数の別解）

次回予告は、ループの開始値/終了値を変化/ズラす制御を学びます。リーグ戦/移動平均/文字列比較に活用できます。＞【擬似言語⑪】リーグ戦と文字列比較 | ずらしループと図解のNote

最後に私のお薦めの演習順番。
❶学習前の”分からせ”
＞【FEB】サンプル問題2のNote
❷テキスト
＞【FEB】擬似言語の教科書Note
＞【FEB】擬似言語の理解演習Note ←いまこの辺
↓※必要なら
うかる！ 基本情報技術者　[科目B・セキュリティ編](amazon)
うかる！ 基本情報技術者　[科目B・アルゴリズム編](amazon)
❸各年度の公開問題
＞【FEB】令和07年科目BのNote
＞【FEB】令和06年科目BのNote
＞【FEB】令和05年科目BのNote
➍解法の総復習（➋や➌と併用可）
＞【FEB】擬似言語の11の解法Note
➎模擬試験
＞【FEB】サンプル問題1のNote（擬似言語）
＞【FEB】サンプル問題1のNote（セキュリティ）