Pythonアルゴリズム

Pythonで再帰を使って階乗を計算する

このレッスンでは、再帰関数で階乗を計算し、停止条件の役割を学びます。

  • 中級
  • 約2分で読めます
  • 実行できるサンプル 1 件

はじめに

どんな問題を解決するか

自分自身の小さな版で自然に説明できる問題があります。フォルダーはフォルダーを含み、家系図はより小さな家系図を含み、n! は n × (n - 1)! です。再帰を使うと、そうした定義どおりにコードを書けます。

身近なたとえ

再帰は、一列に並んだ人たちが質問を順に回していくようなものです。6! を答えるために、先頭の人は隣の人に 5! はいくつかと聞いて、答えを待ちます。その人はさらに 4! を聞き、これを続けていくと、1! を聞かれた人がすぐに答えられます。そこから答えが列を逆にたどって戻り、一人ひとりが自分の数を掛けていきます。

一列に並んだ人からコードへ
factorial(6)🙋 先頭の人: 6 × 待っている答え
number * factorial(number - 1)➡️ 隣の人に、もっと小さい数で同じ質問をする
if number <= 1: return 1🛑 最後の人はすぐに答える: 1
720⬅️ 答えが列を逆にたどって戻る: 720
どの呼び出しも、基本ケースが答えるまで小さな呼び出しを待ちます。
ひと言でいうと

再帰関数は、すぐに答えられる基本ケースに達するまで、より小さな入力で自分自身を呼び出します。ここでは factorial(n) = n × factorial(n - 1)、factorial(1) = 1 です。

重要なポイント

  1. if number <= 1: return 1 は基本ケースで、これがないと呼び出しが止まりません。
  2. return number * factorial(number - 1) は小さい数で同じ関数を呼び出します。
  3. factorial(6) は factorial(5) を待ち、それは factorial(4) を待ち、factorial(1) まで続きます。
  4. raise ValueError(...) は、基本ケースに決して届かない負の数を拒否します。

どんな場面で使う?

  • 木、フォルダー、入れ子のデータなど、小さな版で定義される問題。
  • マージソートのような分割統治アルゴリズム。
  • 呼び出しスタックの仕組みを学ぶ。

使わなくてよいとき

  • 実際のコードでの階乗のような単純な繰り返し:ループや math.factorial のほうが速く、深さの上限もありません。
  • 非常に深い入力:Python は約1,000段の入れ子の呼び出しで RecursionError を出して止まります。

動きで理解する

ステップを押して各呼び出しを追いましょう。新しい呼び出しはコールスタックに積まれ、それぞれ呼び出し元に値を返します。

サンプルコード

コードを実行 →
main.py
def factorial(number):
    if number < 0:
        raise ValueError("Factorial is undefined for negative numbers")
    if number <= 1:
        return 1
    return number * factorial(number - 1)

print(factorial(6))
この例の実行ボタンを作成

実行結果

720

コードの解説

numberが0か1のとき、関数はすぐに1を返します。これが再帰を無限に続けさせないための基底ケースです。それ以外の値では、numberにfactorial(number - 1)を掛けた値を返します。再帰呼び出しは1回ごとに呼び出しスタック(call stack)に積まれるので、再帰の深さはO(n)になります。

値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。

発展問題

下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。

  1. 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
  2. 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
  3. 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
Pythonコンパイラで実行 →

よくある間違い

基本ケースを忘れる

関数は Python が RecursionError を出すまで自分を呼び続けます。

問題
def factorial(number):
    return number * factorial(number - 1)
修正
def factorial(number):
    if number <= 1:
        return 1
    return number * factorial(number - 1)

このレッスンを終えましたか?

学習済みにすると進み具合を記録できます。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

すべてのチャレンジ