再帰関数を理解するための最もシンプルな例
はじめに
再帰関数を理解するにあたり先輩社員に教えていただいたのですが、その時の再帰関数の例がとてもわかりやすかったので共有させていただきます。
この例のおかげもあり、はじめは再帰関数なにそれ状態から最後はしっかりと実装できるようになりました。
再帰関数は Python で実装していますが特に難しいことは書いていません。適宜自分の得意な言語に置き換えて読んでいただければ幸いです。
再帰関数を実装する前に
再帰関数を実装する前に再帰関数を用いる 理由 と ルール に関して知っておくと、理解が早く進むのではないかと思います。
再帰関数を用いる理由とルールに関しては「独学プログラマー」がわかりやすいので引用させていただきます。
まず、再帰関数を用いる理由に関してはこう説明されています。
再帰は、大きな問題を小さな問題に分割して解決する分割統治法で使われる手法で、
小さな問題は比較的楽に解決できるだろう、という点に着目しています。
（中略）
反復法で解決できるどんな問題も、再帰法に置き換えられます。
その上、再帰法はより洗練された解決法となることがあります。
そして、再帰のルールに関してです。
- 再帰法は、再帰終了条件を持たなければならない。
- 再帰法は、状態を変えながら再帰終了条件に進んでいかなければならない。
- 再帰法は、再帰的に関数自身を呼び出さなければならない。
これで なぜ再帰関数を使うと良いのか、 どのように再帰関数を実装すれば良いか がなんとなく理解できたでしょうか。
それでは実際の再帰関数を紹介します。
実際の再帰関数の例を見るとより理解が捗るかと思います。
再帰関数の最もシンプルな例
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
となります。このように再帰関数は状態を変えながら関数自身を再帰的に呼び続けることがわかります。
２. 再帰法は、状態を変えながら再帰終了条件に進んでいかなければならない。
３. 再帰法は、再帰的に関数自身を呼び出さなければならない。
おわりに
再帰は、プログラミング入門者が把握するにはかなり厳しいことで悪名高い概念の 1 つです。はじめは混乱するかもしれませんが、心配せずに練習を続けましょう。
by 独学プログラマー
なぜ再帰関数を使うと良いか、どのように再帰関数を実装すれば良いかという理由とルールを把握した上でとにかく実装してみることが再帰関数を理解する近道になると思います。
今回ご紹介させていただいた例はかなりシンプルな問題であるため再帰関数である恩恵が少ないですが、より複雑な問題のときその本領は発揮されます。
こちらの記事で「複雑な JSON から特定のデータを取り出す」という処理を再帰関数で実装しています。より実践的な内容になっているかと思いますのでよろしければ参考にしてみてください。
Discussion