Pythonインタラクティブガイド - ステップ3 関数 (6) - 再帰関数
- 本講座「Pythonインタラクティブガイド」は、手を動かしながらPythonプログラミングの基礎を学べる実践的な入門講座です。
- 「スタイルガイド」では、Pythonで読みやすくきれいなコードを書くためのガイドライン(PEP8)を主に紹介しています。
- 各コード例はその場で実行して結果を確認できます。
ページ再読み込みで元に戻るので、自由に試してみてください。
「ステップ3 関数」の続きです。
3.5. 再帰関数
まずは次のコードを見てみましょう：
このプログラムでは、関数の中で関数自身(factorial)を呼び出しています。
このように、関数が自身を呼び出す仕組みを再帰 (recursion) といい、再帰を行う関数を再帰関数と呼びます。
3.5.1. 再帰関数の基本
再帰関数の動作を理解するには、上記の階乗計算を段階的に追跡すると分かりやすいでしょう。
factorial(5)を呼び出すと、以下のような処理が順番に実行されます：
factorial(5)を実行5 * factorial(4)を返す必要があるが、まずfactorial(4)の結果が必要
factorial(4)を実行4 * factorial(3)を返す必要があるが、まずfactorial(3)の結果が必要
factorial(3)を実行3 * factorial(2)を返す必要があるが、まずfactorial(2)の結果が必要
factorial(2)を実行2 * factorial(1)を返す必要があるが、まずfactorial(1)の結果が必要
factorial(1)を実行n <= 1なので、1を返す
factorial(2)の処理が続行され、2 * 1 = 2を返すfactorial(3)の処理が続行され、3 * 2 = 6を返すfactorial(4)の処理が続行され、4 * 6 = 24を返すfactorial(5)の処理が続行され、5 * 24 = 120を最終結果として返す
次のコードでは、各ステップで何が起きているかを出力して確認できます：
再帰関数を作成する際には、以下の2つの要素が必要です：
- ベースケース（Base Case）：再帰を終了する条件
- 上記の例では
n <= 1のとき、再帰せずに1を返す
- 上記の例では
- 再帰ステップ（Recursive Step）：問題を小さな部分に分解し、自分自身を呼び出す
- 上記の例では
n * factorial(n - 1)で、より小さな問題に分解
- 上記の例では
3.5.2. 再帰関数の活用例
再帰関数は、問題を同じ形の小さな問題に分解できる場合に特に有効です。
代表的な例をいくつか見てみましょう。
フィボナッチ数列
フィボナッチ数列は、前の2つの数の合計が次の数になる以下のような数列です:
0番目:01番目:1n番目: 「n - 1番目の数」 + 「n - 2番目の数」 (n>= 2)
この数列を再帰関数として自然に表現できます:
階層構造の再帰的探索
再帰関数は、階層構造を扱う場面でも効果的です。
以下は、組織構造の辞書データをツリー形式で視覚的に出力する例です:
ネストしたリストを平坦化する関数flattenを、再帰を用いて作成しましょう
(例: flatten([1, [2, [3, 4], 5]) = [1, 2, 3, 4, 5])
解答例
以下のルールに従って、入力された正の整数nが 1 になるまでのステップ数を返す関数 collatz を再帰関数を用いて作成しましょう:
nが1の場合: 処理を終了しますnが偶数の場合:nを2で割りますnが奇数の場合:nを3倍して1を足します
(例: n=6の場合、6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 となるので、collatz(6) = 8)
解答例
3.5.3. メモ化
先ほど扱ったフィボナッチ数列を計算する関数 fibonacci は、nが大きくなると計算時間が指数関数的に増加してしまいます:
この問題を解決するためにメモ化（memoization）というテクニックがあります。
メモ化とは、一度計算した結果を記憶しておき、同じ計算が必要になった時に再計算せずに記憶した結果を再利用する手法です。
例えば、fibonacci(5)を計算する場合:
fibonacci(4)+fibonacci(3)を計算fibonacci(4)を計算するにはfibonacci(3)+fibonacci(2)を計算fibonacci(3)を計算するにはfibonacci(2)+fibonacci(1)を計算
このように、同じ引数（例：fibonacci(3)）に対する計算が複数回発生します。
メモ化を使うと、これらの再計算を避けて効率良く結果を得ることができます。
Pythonには、関数を装飾するデコレータという機能があり、functoolsモジュールのcacheデコレータを使うと、関数を簡単にメモ化できます (デコレータについては後ほど詳しく説明します):
- メモ化は、同じ引数に対して常に同じ戻り値を返す関数に有効です。
同じ引数でもタイミングによって結果が変わる関数（例：現在時刻を返す関数）では、意図しない動作の原因になるため注意が必要です。 - メモ化はメモリを消費するため、使用するメモリ量と処理速度のトレードオフを考慮する必要があります。
functoolsのcacheデコレータを使用する場合、関数の引数はイミュータブル（ハッシュ化可能）である必要があります。
フィボナッチ数列の単純な再帰実装と、メモ化を使用した実装の計算量には大きな違いがあります。
単純な再帰実装の計算量
単純な再帰を使用したフィボナッチ数列の計算は、O(2^n) の時間計算量になります。
これは各呼び出しが2つの再帰呼び出しを生成し、同じ値を何度も再計算するためです。
例えば fibonacci(5) を計算する場合:
fibonacci(5)はfibonacci(4)とfibonacci(3)を計算fibonacci(4)はfibonacci(3)とfibonacci(2)を計算fibonacci(3)はfibonacci(2)とfibonacci(1)を計算
このように、fibonacci(3) や fibonacci(2) が複数回計算されることで、計算回数が指数関数的に増加します。
graph TD
F5["fibonacci(5)"]
F54["fibonacci(4)"]
F543["fibonacci(3)"]
F5432["fibonacci(2)"]
F5431["fibonacci(1)"]
F54321["fibonacci(1)"]
F54320["fibonacci(0)"]
F542["fibonacci(2)"]
F5421["fibonacci(1)"]
F5420["fibonacci(0)"]
F53["fibonacci(3)"]
F532["fibonacci(2)"]
F5321["fibonacci(1)"]
F5320["fibonacci(0)"]
F531["fibonacci(1)"]
F5 --> F54
F5 --> F53
F54 --> F543
F54 --> F542
F543 --> F5432
F543 --> F5431
F5432 --> F54321
F5432 --> F54320
F542 --> F5421
F542 --> F5420
F53 --> F532
F53 --> F531
F532 --> F5321
F532 --> F5320
メモ化による改善
メモ化を使用すると、計算量は O(n) に劇的に改善されます。
例えば fibonacci(5) を計算する場合、fibonacci(4) ~ fibonacci(0) の値が各々複数回必要となりますが、一度計算した結果を記憶するため、実質5回分の計算で済むことになります。
graph TD
F5["fibonacci(5)"]
F54["fibonacci(4)"]
F543["fibonacci(3)"]
F5432["fibonacci(2)"]
F5431["fibonacci(1)"]
F54321["fibonacci(1)"]
F54320["fibonacci(0)"]
F542["fibonacci(2)"]
F5421["fibonacci(1)"]
F5420["fibonacci(0)"]
F53["fibonacci(3)"]
F532["fibonacci(2)"]
F5321["fibonacci(1)"]
F5320["fibonacci(0)"]
F531["fibonacci(1)"]
F5 --> F54
F5 -. メモから取得 .-> F53
F54 --> F543
F54 -. メモから取得 .-> F542
F543 --> F5432
F543 -. メモから取得 .-> F5431
F5432 --> F54321
F5432 --> F54320
F542 -.-> F5421
F542 -.-> F5420
F53 -.-> F532
F53 -.-> F531
F532 -.-> F5321
F532 -.-> F5320
%% メモ化でたどり着いたノードをグレー枠・グレー背景・半透明で
style F5431 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3
style F542 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3
style F542 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3
style F5421 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3
style F5420 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3
style F53 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3
style F532 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3
style F5321 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3
style F5320 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3
style F531 fill:#cccccc,stroke:#666666,stroke-width:2px,opacity:0.3
以下はベンチマークライブラリを使用した、単純な再帰実装とメモ化実装の速度比較です:
ベンチマーク結果からも、メモ化なしの場合は計算量が指数関数的に増加して、
メモ化ありの場合は高速に動作することがわかります。
3.5.4. 再帰の深さ
再帰関数が呼び出されるたび、その関数の実行に必要な情報（ローカル変数、引数、戻り先など）は「スタックフレーム」としてメモリ上のスタック領域に積み重ねられていきます。
スタック領域のサイズには限りがあるため、再帰の深さには上限が設けられています。
関数が呼び出されると、コンピュータは「スタックフレーム」と呼ばれるメモリ領域を確保します。
このフレームには、関数の実行に必要な情報（ローカル変数、引数、戻り先アドレスなど）が保存されます。
再帰関数では、次のようにスタックフレームが扱われます：
- 関数が自分自身を呼び出すたびに、新しいスタックフレームが積み重なっていく
- 関数の処理が終わると、そのスタックフレームが取り除かれる（解放される）
- 深い再帰では、多数のフレームが一時的に同時に存在することになる
graph TD
A["factorial(5)
n=5"] --> B["factorial(4)
n=4"]
B --> C["factorial(3)
n=3"]
C --> D["factorial(2)
n=2"]
D --> E["factorial(1)
n=1"]
上図は、再帰的なfactorial関数の呼び出しにともなって形成されるスタックフレームのイメージです。
再帰の最大深度に到達すると、Pythonは RecursionError を発生させます:
Pythonにおける再帰の深さ制限は、プラットフォーム（OSやPythonの実装）によって異なる場合がありますが、一般的には1000程度に設定されています。以下のコードで確認できます：
この制限は sys.setrecursionlimit() によって変更可能ですが、制限を大きくしすぎるとメモリを使い果たし、スタックオーバーフローと呼ばれるエラーが発生するおそれがあります:
- 再帰の深さ制限を上げることは一時的な対処にすぎません
- 根本的な解決には、アルゴリズムの見直し（ループによる反復処理への置き換えやメモ化の導入）が効果的です
- 深すぎる再帰は、スタックオーバーフローの原因となるだけでなく、処理効率の低下も招きます
3.5.5. 再帰とループ
再帰で表現できる処理は、多くの場合ループ（繰り返し処理）でも表現できます。
例えば、階乗の計算をループで行うと次のようになります：
再帰とループのどちらを選ぶかは、以下の点を考慮して判断します：
- 可読性: 問題によっては、再帰の方が自然で理解しやすい表現になる場合があります
- 効率性: 一般的に、ループの方がメモリ使用量が少なく効率的です
- 制限: 再帰は深さに制限があるため、大きな入力では制限に達する可能性があります
前の練習問題で扱ったcollatz関数は、再帰を用いているため最大深度の制限があります。
任意の整数でcollatz関数を動作させるため、while文を用いた実装に書き換えましょう。
解答例
まとめ
この節では、再帰関数について以下のポイントを学びました：
- 再帰関数の概念: 関数が自分自身を呼び出す仕組み
- ベースケースと再帰ステップ: 再帰関数を正しく動作させるための2つの重要な要素
- 再帰の活用例: 階乗、フィボナッチ数列、階層構造の探索など
- メモ化: 再帰計算を効率化するための重要なテクニック
- 再帰の深さ: 再帰には実行環境に応じた深さの制限がある
- 再帰とループの比較: それぞれの長所と短所、使い分けのポイント
再帰は、複雑な処理をシンプルに記述できる強力な手法です。
一方で、無限再帰やスタックオーバーフローといった落とし穴もあるため、その仕組みと制限を正しく理解したうえで活用することが重要です。