はじめに

こちらの記事で複雑なJSONから特定のデータを取得するために再帰関数で実装したのですが、初めは再帰関数なにそれ状態から、最後にはしっかりと理解して実装できるようになりました。

そこで今回は、私が再帰関数を理解するにあたり一番最初に先輩社員に教えていただいた再帰関数の例をご紹介します。

再帰関数を実装する前に

再帰関数を実装する前に、再帰関数を用いる理由と ルール に関して知っておくと、理解が早く進むのではないかと思います。

再帰関数を用いる理由とルールに関しては、独学プログラマーがわかりやすいので引用させていただきます。

まず、再帰関数を用いる理由に関してはこう説明されています。

再帰は、大きな問題を小さな問題に分割して解決する分割統治法で使われる手法で、小さな問題は比較的楽に解決できるだろう、という点に着目しています。（中略）反復法で解決できるどんな問題も、再帰法に置き換えられます。その上、再帰法はより洗練された解決法となることがあります。

そして、再帰のルールに関してです。

再帰法は、再帰終了条件を持たなければならない。

再帰法は、状態を変えながら再帰終了条件に進んでいかなければならない。

再帰法は、再帰的に関数自身を呼び出さなければならない。

詳細に関しては実際に独学プログラマーを読んでみてください。

再帰関数を勉強するにあたり、個人的に一番シンプルでわかりやすいと感じた再帰関数の例です。

def sum(n):
    if n <= 0:
        return n
    return n + sum(n-1)

名前があまり良くないですが、1からnまでの自然数の和を返す関数です。例えば、n=10だった場合、sum関数の戻り値は、

10 + sum(10-1)

sum(10-1) = sum(9)の戻り値は、

9 + sum(9-1)

sum(9-1) = sum(8)の戻り値は、、、、、

のようにsum関数は自分自身を呼び出し続けます。そして、n=0のとき、

if n <= 0:
    return 0

0を返します。nが0以下がこの再帰関数の再帰終了条件にあたります。

以上からsum(10)の返り値は、

10 + 9 + 8 + ... + 1 + 0 = 55

となります。このように再帰関数は、状態を変えながら関数自身を再帰的に呼び続けることがわかります。

再帰関数は、プログラミング初学者にとってはすごく難しい概念だと思うので、理解のお役に立てれば嬉しいです。