タスクを繰り返すことを考えるとき、私たちは通常 for と while ループを思い浮かべます。これらの構文によって、リストやコレクションなどの反復処理を行うことができます。
しかし、タスクを繰り返す方法には、少し違った方法もあります。同じ問題のより小さなインスタンスを解決するために、それ自身の中で関数を呼び出すことで、再帰を実行しているのです。
例えば、大きな食べ物を一口ずつ食べるように、最初の問題を小さなインスタンスに分割していくのです。
例えば、大きな食べ物を少しずつ食べるというようなことです。最終的な目標は、ホットポケットの皿を全部食べることですが、そのためには一口ずつ何度も食べる必要があります。一口食べるごとに再帰的なアクションが発生し、次に同じアクションを行う。一口食べるごとに、「もう一口食べたらゴールだ」と評価し、皿にホットポケットがなくなるまで、これを繰り返す。
再帰性とは？
冒頭で述べたように、再帰は定義上、自分自身を呼び出す処理を伴う。再帰的な関数は、一般的に2つの構成要素を持っています。
- 基本ケース：再帰関数を停止するタイミングを決定する条件です。
- 自分自身への呼び出し
この2つの構成要素を説明するために、小さな例を見てみよう。
# Assume that remaining is a positive integer
def hi_recursive(remaining):
# The base case
if remaining == 0:
return
print('hi')
# Call to function, with a reduced remaining count
hi_recursive(remaining - 1)
ベースケースは、変数 remaining が 0 に等しいかどうか、つまり “hi” という文字列があといくつ表示されなければならないか、ということです。この関数は単純に返します。
print 文の後、再び hi_recursive を呼び出しますが、このとき残りの値は小さくなっています。これは重要です! もし remaining の値を減らさなければ、この関数は無限に実行されることになります。一般に、再帰的な関数が自分自身を呼び出すとき、パラメータは基本ケースに近づくように変更されます。
それでは、hi_recursive(3) を呼び出したときにどのように動作するかを見てみましょう。
この関数は ‘hi’ を表示した後、0 に達するまで remaining に低い値を指定して自分自身を呼び出します。0 になると、この関数は hi_recursive(1) で呼ばれた場所に戻り、さらに hi_recursive(2) で呼ばれた場所に戻り、最終的に hi_recursive(3) で呼ばれた場所に戻ることになります。
なぜLoopを使わないのか？
すべてのトラバーサルはループで処理できる。それでも、問題によっては反復処理より再帰処理の方が簡単に解決できることもある。再帰の一般的な使用例は、木の探索です。
というものです。
木のノードとリーフを走査するのは、通常、再帰を使用する方が考えやすい。ループと再帰はどちらも木を走査しますが、その目的は異なります。ループはタスクを繰り返すことを目的としているのに対し、再帰は大きなタスクを小さなタスクに分割することを目的としています。
例えば木を使った再帰処理は、木の小さな部分を個別に処理することで木全体を処理することができるので、うまくフォークします。
例
再帰や他のプログラミングの概念に慣れるには、実践することが一番です。再帰関数の作成は簡単で、ベースケースを必ず記述し、ベースケースに近づくように関数を呼び出す。
リストの和
Python にはリストに対する sum 関数があります。Pythonのデフォルト実装であるCPythonでは、これらの関数を作るためにC言語の不定形なfor-loopを使っています（興味のある方はこちらのソースコードをご覧ください）。では、再帰を使ってどうやるか見てみましょう。
def sum_recursive(nums):
if len(nums) == 0:
return 0
last_num = nums.pop()
return last_num + sum_recursive(nums)
ベースケースは空のリストで、それに対する最適な sum は 0 です。ベースケースを処理したら、リストの最後の項目を削除します。最後に、縮小されたリストで sum_recursive 関数を呼び出して、取り出した数を合計に追加します。
Python インタープリタでは、 sum([10, 5, 2]) と sum_recursive([10, 5, 2]) は両方とも 17 となるはずです。
階乗数
正の整数の階乗は、その前にあるすべての整数の積であることを思い出すかもしれない。次のような例がわかりやすいだろう。
5! = 5 x 4 x 3 x 2 x 1 = 120
感嘆符は階乗を表し、5に4から1までのすべての整数の積を掛けていることがわかる。もし誰かが0を入力したらどうなるのでしょうか？0! = 1 であることは広く理解され、証明されています。では、次のような関数を作ってみましょう。
def factorial(n):
if n == 0 or n == 1:
return 1
return n * factorial(n - 1)
1や0が入力された場合に対応し、それ以外の場合は、現在の数値に1` で減らした数値の階乗を掛けています。
Python インタープリタで簡単に検証すると、 factorial(5) で 120 となることがわかります。
フィボナッチ数列
フィボナッチ数列とは、各数値が次の2つの数値の和である数列のことである。この数列は、0と1のフィボナッチ数が0と1であることを仮定している。したがって、2のフィボナッチ数は1になる。
それでは、数列とそれに対応する自然数を見てみよう。
Integers: 0, 1, 2, 3, 4, 5, 6, 7
Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13
Pythonで再帰を使って任意の正の整数のフィボナッチ等価数を求める関数を簡単にコーディングすることができます。
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
fibonacci(6)が8` に等しいことを確認することで、期待通りに動くことを確認することができます。
ここで、この関数のforループを使った別の実装を考えてみてほしい。
def fibonacci_iterative(n):
if n <= 1:
return n
a = 0
b = 1
for i in range(n):
temp = a
a = b
b = b + temp
return a
もし整数が1以下であれば、それを返します。さて、これで基本的なケースは処理された。最初の数値を更新する前に temp 変数に格納しておくことで、最初の数値と2番目の数値を連続的に足し算しているのです。
出力は最初の fibonacci() 関数と同じです。Python の実装は再帰的な処理には最適化されていませんが、命令的なプログラミングには優れているので、このバージョンは再帰的なものよりも高速に処理できます。しかし、この解答は最初の試みほど読みやすいものではありません。そこには、再帰の最大の強みであるエレガントさがある。プログラミングの解決策の中には、再帰を使って最も自然に解けるものがある。
結論
再帰は、自分自身を繰り返し呼び出すことで、大きなタスクを小さなタスクに分解することができます。再帰的な関数は、実行を停止するためのベースケースと、徐々にベースケースに関数を導く自分自身への呼び出しを必要とします。木でよく使われるが、他の関数も再帰を使って書くことでエレガントな解決策を提供することができる。