再帰関数(Recursive Function)と繰り返し処理（Iteration)

関数の中でその関数自身を呼び出すものを再帰関数と言います。

再帰関数でできることは全て繰り返し処理で解決できるためあまり使うことはなさそうですが、トポロジカルソートのような特定の場面には威力を発揮します。

階乗(factorial)の計算

例として、階乗をそれぞれ再帰関数と繰り返し処理で計算してみます。

(1)再帰関数の場合

def factorial_recursive(n):
    if n == 2:
        return 2
    elif n == 1:
        return 1
    elif n == 0:
        return 1
    return n*factorial_recursive(n-1)

ベースケースはn=2の時に２を返すという処理ですが、例外的にnが１と0の時は１を返すよう定義します。

(2)繰り返し処理の場合

def factorial_iterative(n):
    result = 1
    for i in range(1,n+1):
        result *= i
    return result

繰り返し処理の場合は初期値に１を設定しそれに次々と掛けて代入していくため、階乗の定義とは逆になります。この場合、初期値は１に設定しているため、nが0,1の時は1を返します。

フィボナッチ数列の一般項

次に２つの処理でフィボナッチ数列の一般項を求める処理を記述してみます。

(1)再帰処理の場合

def fibo_recursive(n):
    if n < 2:
        return n
    return fibo_recursive(n-1) + fibo_recursive(n-2)

再帰処理で記述する場合かなりシンプルに書くことができます。（計算は後ろから行っています。）

(2)繰り返し処理の場合

def fibo_iterative(n):
    a = 0
    b = 1
    if n == 0:
        return a
    elif n == 1:
        return b 
    else:
        for i in range(n-1):
            tmp = a + b 
            a = b 
            b = tmp 
        return tmp 

繰り返し処理の場合は一時的な変数tmpを作成し、そこに次の数値を代入していきます。

また、nが0,1の時は初期値1およびbを返すように条件分岐を組めば全ての整数に対応できます。

計算量の比較

(1)階乗計算の場合

この場合はどちらの処理も前の数に次の数をかけ合わせていっているため、計算量はO(n)となります。

(2)フィボナッチ数列の場合

繰り返し処理の場合、一時変数を使って足し算を繰り返しているため計算量はO(n)で済みます。

しかし、再帰関数を使うと後ろから計算していっているため、最悪の場合O(2^n)となってしまいます。

使うところはトポロジカルソートや二分探索などに限定されますが、知っておいて損はないかと思います。