再帰関数の処理される順番

Pythonでアルゴリズムの学習中に再帰関数を学んだが、「再帰関数でループしたらその下の行の処理いかないんじゃね？」みたいな感じで処理の順番があやふやなところが多いので、下の例を実装しながら理解を深めていく。

再帰関数とは

定義中の関数の中で、その関数（自分自身）が呼び出される関数のこと。「再帰呼び出し」とも呼ばれる。
繰り返し処理などで使われる。

実装

再帰関数totalでどのような値が出力されるか考える。

Python

def total(data):
    if data <= 1:
        return data

    value = total(data - 1)

    return sum(value)


def sum(value):
    return value + 3


print(total(3))

まず、引数に3が入れられたtotal関数が呼び出される。ここで、引数dataが1以下の場合は「1」が返されるが、現状は3なので無視。

次に、変数valueが定義されているが、ここで同じ関数が呼び出される(再帰呼び出し)。引数はdata - 1なので、2になる。ここではreturn sum(value)に進まず、total関数が再び上から処理される。引数dataは2で１以上なのでdataはreturnされず、再び変数valueが定義される（引数は1）。ここでついに引数dataが1になったので、1がreturnされ（無限ループすることはない）、引数が2のtotal関数の変数valueの値は1になる。そして、return sum(value)に進むことができる。

sum関数は引数に+ 3した値を返すだけなので、ここでは1 + 3 で4が返される。ここで、引数が2のtotal関数は4が返されたので、引数が3のtotal関数の変数valueに4が与えられる。そして、return sum(value)に進み、4 + 3で7が返され、7が出力される（引数が3のtotal関数を出力するのでこれで終わり）。

まとめ

様々なソートのアルゴリズムで難しい再帰関数の使われ方がされており、理解に苦しんでいたが、これを機に少しは楽になった。再帰関数はあまり使うことはないと思うが、頭の片隅にでも入れておくと良いだろうと思った。