Python
再帰関数

再帰関数を理解するための最もシンプルな例

はじめに

再帰関数を理解するにあたり先輩社員に教えていただいたのですが、その時の再帰関数の例がとてもわかりやすかったので共有させていただきます。

この例のおかげもあり、はじめは再帰関数なにそれ状態から、最後はしっかりと実装できるようになりました。再帰関数はPythonで実装しています。

再帰関数を実装する前に

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

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

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

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

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

  1. 再帰法は、再帰終了条件を持たなければならない。
  2. 再帰法は、状態を変えながら再帰終了条件に進んでいかなければならない。
  3. 再帰法は、再帰的に関数自身を呼び出さなければならない。

これで、 なぜ再帰関数を使うと良いのかどのように再帰関数を実装すれば良いか がなんとなく理解できたでしょうか。

それでは、実際の再帰関数を紹介します。
実際の再帰関数の例を見るとより理解が捗るかと思います。

再帰関数の最もシンプルな例

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以下 がこの再帰関数の再帰終了条件にあたります。

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

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

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

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

2. 再帰法は、状態を変えながら再帰終了条件に進んでいかなければならない。
3. 再帰法は、再帰的に関数自身を呼び出さなければならない。

おわりに

再帰は、プログラミング入門者が把握するにはかなり厳しいことで悪名高い概念の1つです。はじめは混乱するかもしれませんが、心配せずに練習を続けましょう。

by 独学プログラマー

なぜ再帰関数を使うと良いか、どのように再帰関数を実装すれば良いかという理由とルールを把握した上で、とにかく実装してみることが再帰関数を理解する近道になると思います。

今回ご紹介させていただいた例は、かなりシンプルな問題であるため再帰関数である恩恵が少ないですが、より複雑な問題のとき、その本領は発揮されます。

複雑なJSONから特定のデータを取り出す

こちらの記事で「複雑なJSONから特定のデータを取り出す」という処理を再帰関数で実装しています。より実践的な内容になっているかと思いますので、よろしければ参考にしてみてください。