はじめに
どんな問題を解決するか
自分自身の小さな版で自然に説明できる問題があります。フォルダーはフォルダーを含み、家系図はより小さな家系図を含み、n! は n × (n - 1)! です。再帰を使うと、そうした定義どおりにコードを書けます。
身近なたとえ
再帰は、一列に並んだ人たちが質問を順に回していくようなものです。6! を答えるために、先頭の人は隣の人に 5! はいくつかと聞いて、答えを待ちます。その人はさらに 4! を聞き、これを続けていくと、1! を聞かれた人がすぐに答えられます。そこから答えが列を逆にたどって戻り、一人ひとりが自分の数を掛けていきます。
factorial(6)🙋 先頭の人: 6 × 待っている答えnumber * factorial(number - 1)➡️ 隣の人に、もっと小さい数で同じ質問をするif number <= 1: return 1🛑 最後の人はすぐに答える: 1720⬅️ 答えが列を逆にたどって戻る: 720再帰関数は、すぐに答えられる基本ケースに達するまで、より小さな入力で自分自身を呼び出します。ここでは factorial(n) = n × factorial(n - 1)、factorial(1) = 1 です。
重要なポイント
if number <= 1: return 1は基本ケースで、これがないと呼び出しが止まりません。return number * factorial(number - 1)は小さい数で同じ関数を呼び出します。factorial(6)はfactorial(5)を待ち、それはfactorial(4)を待ち、factorial(1)まで続きます。raise ValueError(...)は、基本ケースに決して届かない負の数を拒否します。
どんな場面で使う?
- 木、フォルダー、入れ子のデータなど、小さな版で定義される問題。
- マージソートのような分割統治アルゴリズム。
- 呼び出しスタックの仕組みを学ぶ。
使わなくてよいとき
- 実際のコードでの階乗のような単純な繰り返し:ループや
math.factorialのほうが速く、深さの上限もありません。 - 非常に深い入力:Python は約1,000段の入れ子の呼び出しで RecursionError を出して止まります。
動きで理解する
ステップを押して各呼び出しを追いましょう。新しい呼び出しはコールスタックに積まれ、それぞれ呼び出し元に値を返します。
サンプルコード
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つだけのリスト、重複した値を含むリストで試す。
- 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
- 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
よくある間違い
基本ケースを忘れる
関数は Python が RecursionError を出すまで自分を呼び続けます。
def factorial(number):
return number * factorial(number - 1)
def factorial(number):
if number <= 1:
return 1
return number * factorial(number - 1)
このレッスンを終えましたか?
学習済みにすると進み具合を記録できます。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
すべてのチャレンジ