再帰呼び出しは高度なプログラミング言語の基本的な特性であり、最初はLISP言語に現れました。Python言語も再帰呼び出しをサポートしています。再帰呼び出しを通じてコードを簡素化することができ、しかもコードを問題の数学的な記述と非常に一致させることができます。再帰呼び出しを使用しても一般的にコードの実行速度は向上しません。

再帰呼び出しとは

再帰呼び出しは特殊なネスト呼び出しであり、ある関数が自身を呼び出すか、他の関数を呼び出した後に再度自身を呼び出すことを指します。無限にネスト呼び出しすることはできないため、ある再帰関数には必ず少なくとも2つの分岐が存在します。1つはネストを終了し、直接的または間接的に自身を呼び出さない分岐で、もう1つはネストを続ける分岐です。

一般的に関数の入力パラメータによってどの分岐をたどるかを決定するため、再帰関数は一般的にパラメータを持っています。

再帰呼び出しの例

1、階乗の計算

最も一般的な再帰の使い方は整数の階乗を求めることです。例えば、2の階乗は1×2に等しく、3の階乗は1×2×3に等しいです。再帰的な方法を使わない場合、以下の方法で実装することができます。

>>> def get_factorial(n):                      # 階乗関数を定義
...     ret = i = 1
..     while i <= n:                           # 1からnまで順に乗算
...             ret = ret * I
...             i = i + 1
...     return ret                             # 戻り値を返す
...                                           # 階乗関数の定義終了
>>> get_factorial(3)                           # 3の階乗を求める
6
>>> get_factorial(10)                          # 10の階乗を求める
3628800

再帰的な方法を使う場合、以下のような評価方案を定義することができます。

n＞1の場合、階乗関数自身を再帰的に呼び出すことができます。コードは以下の通りです。

>>> def get_factorial(n):                              # 階乗関数を定義
...     if n == 1:                                     # 再帰を終了する分岐
...         return 1
...     return n * get_factorial(n-1)   # 再帰呼び出し
...                                                   # 階乗関数の定義終了
>>> get_factorial(3)                                   # 3の階乗を求める
6
>>> get_factorial(10)                                  # 10の階乗を求める
3628800

再帰には再帰の深さに注意する必要があります。再帰は複数回の関数呼び出しを生み出し、関数呼び出しはコードのスタック領域を消費します。再帰の深さが大きすぎると、スタックオーバーフローが発生します。上記の階乗の例では、100000の階乗を計算すると、一般的なマシンではスタックオーバーフローの問題が発生します。以下に示します。

>>> get_factorial(100000)             # 100000の階乗を求める
Traceback (most recent call last):    # エラーメッセージ
File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in get_factorial
  File "<stdin>", line 4, in get_factorial
  File "<stdin>", line 4, in get_factorial
  [Previous line repeated 994 more times]
  File "<stdin>", line 2, in get_factorial
RecursionError: maximum recursion depth exceeded in comparison

デフォルトでは、関数呼び出しの深さの最大値は1000です。1000に達するか超えると、上記のエラーメッセージが表示されます。以下のコードでこのシステム設定を確認することができます。

>>> import sys
>>> sys.getrecursionlimit()   # 最大呼び出し深さを取得
1000                    # 現在の値は1000

このシステム値を変更したい場合は、sysモジュールのインターフェース関数を使用して実現することもできます。最大関数呼び出し深さを10000に設定したい場合は、以下のコードを使用して変更することができます。

>>> import sys
>>> sys.setrecursionlimit(10000)               # 最大呼び出し深さを設定

2、フィボナッチ数列

1、1、2、3、5、8、13、21、34…という数列があります。最初の要素と2番目の要素は1に等しく、他の要素はその前の2つの要素の和に等しいです。数学的な公式で表すと以下の通りです。

以下のコードで実装することができます。

>>> def fab(n):          # フィボナッチ数列を定義
...     if n in [1, 2]:  # nが1または2の場合
...         return 1
...     return fab(n-1)+fab(n-2)    # n＞2の場合
...
>>> fab(1)                          # フィボナッチ数列の最初の要素
1
>>> fab(2)                          # フィボナッチ数列の2番目の要素
1
>>> fab(8)                          # フィボナッチ数列の8番目の要素
21
>>> fab(8)                          # フィボナッチ数列の9番目の要素
34

3、順列

入力されたリストについて、要素の位置を変えることで異なる値を得ることができます。順列とは、これらのすべての並び替えのリストを取得することです。一般的に、n個の要素のリストにはn!通りの並び替え方法があります。例えば、[1,2,3]には以下のような並び替え方法があります。

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

以下は再帰的な方法で実装された順列です。

>>> def sub_combination(left, right):  # leftは左側の処理待ちのリストを表す
...     if len(left) > 0:              # 処理が完了していない場合
...         for item in left:          # 処理が完了していない要素から1つ