【Python】再帰関数をシンプルな例題で理解する

Python
2020.01.25

再帰関数ってややこしいですよね。

この記事では再帰関数について、シンプルな例題を実際にPythonでプログラミングしながら解説していきます。

解説は以下の書籍を参考にしています。プログラミングの一般教養が楽しく学べるおすすめの一冊です。

コーディングを支える技術 成り立ちから学ぶプログラミング作法
本書は、プログラミング言語が持つ各種概念が「なぜ」存在するのかを解説する書籍です。世の中にはたくさんのプログラミング言語があります。そしてプログラミングに関する概念も、関数、型、スコープ、クラス、継承など、さまざまなものがあります。多くの言語で共通して使われる概念もあれば、一部の言語でしか使われない概念もあります。これらの概念は、なぜ生まれたのでしょうか。本書のテーマは、その「なぜ」を理解することです。

再帰関数って何？

そもそも再帰関数とは何かというと

再帰呼び出し（ある関数Xの中から関数X自体を呼び出す処理）を行う関数

です。

再帰関数が無いとプログラムが書けないということはまず無いですが、これが使えるととても便利です。

具体的には、「ある関数で処理を行っている最中に、その関数で行っている同じ処理を”別の対象（引数）”に対しても行いたい」という要望に応えてくれます。

この説明だけでは、何のことかよく分からないので、具体的な問題で考えていきましょう。

例題：入れ子リストの数値を全部足し合わせる

ここでは、[1, [2, 3], 4]というリストの中にリストがあるような、入れ子のリストに含まれる数字を全部足す問題を考えます。

さて、この[1, [2, 3], 4]に含まれる数字の合計を計算するプログラムをどうやって書きましょう。

[1, [2, 3], 4]は２重の入れ子なので、forの2重ループで頑張れば解けそうです。でももしこれが3重、4重になったらどうでしょう？その度にforループを増やすのは現実的じゃないですね。

そこで再帰呼び出しを使って、合計値を計算するプログラムを書きましょう。

def calculate_total(items: list):
    result = 0
    for item in items:
        # itemが整数の場合
        if isinstance(item, int):
            result += item
        else:
            # TODO: itemが整数ではない場合はどうする？
            pass
    return result

これはリストを引数にとって、そのリストをfor文で回し、その要素が整数か否かで処理を変える関数です。関数中のifでitemが整数の場合の場合に、resultに足し合わせる処理をしています。

しかし、else（itemが整数ではない場合）の処理は何もしていない（passしている）ので、これでは当然正しい合計値の計算ができません。以下のような結果になってしまいます。

>>> calculate_total(nested_list)
5




ではpassの部分をどう変更したら良いでしょうか。

いま私たちは、itemが整数ではない（この問題ではitemがリストのとき）の処理を考えています。

ここでやるべきことは、リストを引数にとって、そのリストの要素が整数の場合には、その合計値を計算することです。

ここで重要なことに気がつきます。

そうです、私たちが今書いている関数calculate_total()は、まさにそれと同じ処理をしようとしているものでした。リストを引数にとって、その要素が整数の場合にそれらの値を足し合わせる処理です。

ですから、このelseの中でも、この関数自身を呼び出して使ってしまえば良いのです。

そうすると、リストの要素にリストが含まれる限り、再帰的に合計を求めるための処理をしてくれるようになります。

def calculate_total(items: list):
    result = 0
    for item in items:
        # itemが整数の場合
        if isinstance(item, int):
            result += item
        else:
            result += calculate_total(item)
    return result
>>> calculate_total(nested_list)
10

このように正しく計算することができました。この関数はネストが3重4重になっても、問題無く動きます。

ここで1つ気をつけたいのは、elseの中で関数calculate_total()を呼び出す時に、その戻り値をresultに足し込むのを忘れないことです。意外と忘れてしまうので要注意です。

以上で、再帰関数の説明はおしまいです。お付き合い頂き、ありがとうございました。

コメント