Python 再帰処理とは？

pythonでは反復処理をするときfor文や内包表記がよく使われますが、再帰関数というテクニックを使って実装することもできます。今回は再帰処理や、再帰関数について説明します。

ちなみに、関数型プログラミング言語の代表であるHaskellはfor文やwhile文はありません。繰り返し処理は再帰を使って実現しています。

再帰処理

関数型プログラミングでは関数を使って反復処理を実装する方法が主流です。

利用することはあまりないですが、関数型プログラミングにおいて重要な概念なので取り上げます。

再帰関数は次の条件を満たす必要があります。

1. 基底部：終了条件を定義する
2. 再帰部：終了条件に近づくように、再帰呼び出しをする

再帰関数を学ぶためには具体例をいくつも読んで、理解できるまで何度も処理の流れを追うのが良いです。

1～10の総和を求めるコードを紹介します。

for文を使う

１つ目はfor文を使った方法です。range(1, 11)で1から10までの整数を順番に呼び出し、xに加算しています。

x=0
for i in range(1, 11):
   x += i
print(x)

【結果】

55

再帰関数を使う　その１

2つ目は再帰関数を使った方法です。total_1と言う再帰関数を定義します。

def total_1(x):
    if x == 0:
        return x
    else:
        return x + total_1(x-1)

result = total_1(10)
print(result)

【結果】

55

基底部は

if x == 0:
    return x

の箇所です。終了するときは具体的な値を返しています。

再帰部は

else:
    return x + total_1(x-1)

です。引数をx-1にして自分自身の関数を呼び出しています。

再帰関数を使う　その２

３つ目も再帰呼び出しを使った方法でが２つ目と引数が異なります。

def total_2(x, accumulator):
    if x == 0:
        return accumulator
    else:
        return total_2(x-1, accumulator + x)

result2 = total_2(10,0)
print(result2)

【結果】

55

accumulatorと言う引数に計算結果を保存しています。このような変数を蓄積変数と言います。３つ目の方法はメモ化と言う手法を使って最適化できることがあるため2つ目の方法よりも利点があります。

再帰関数のメリット、デメリット

再帰関数短くかけますが、分かりづらかったりコストがかかるためfor文で実装する方が一般的です。

メリット

• 代入操作が不要
• コードが短くなる
• 帰納法を利用しているため、数学的に正しいと証明できる

デメリット

• for文より反復処理をしていることが分かりづらい
• for文よりロジックが分かりづらい
• 関数を何度も呼ぶためコストがかかる