JavaScript 超初心者向け -- リカージョン(再帰関数) --
JavaScript を学んでいてつまづいたのが再帰関数です。英語のドキュメントでは Recursion と書いてある章です。 ただ、なんとなく理解しているのですが、どうしても自分で書こうとすると書けないものの一つです。これは本当に気持ち悪い書き方だと思いましたが、なんとか読んで理解するまで理解を深めていけましたので、まずはその過程を書いてみたいと思います。
リカージョン(再帰関数)の概念を理解する
「再帰処理」って単語が出てきたら「自分自身を呼び出す処理が書かれている関数を呼び出すことなんだな~」 ( https://wa3.i-3-i.info/word14899.html (概念を理解するのにとても助かりました )
When a function solves a task, in the process it can call many other functions. A partial case of this is when a function calls itself. That’s called recursion.
とにかく自分自身を呼び出す関数なのかと頭では理解できましたが、どうしても自分で書くことができませんでした。
克服方法
関数は値であるということをよく理解する
Functions are values. や 関数は値である といろいろなドキュメントで見かけますが、このことによく気づくとリカージョンの理解が一歩進みました。 関数がその自分自身の関数を呼ぶという、文で見ると簡単ではありますが、実際に理解するとき脳が停止しました。 しかし、関数が値(形を変えていく値という風に理解するとさらによく理解できましたが。。)であれば、方程式に代入することはよくあることです。a = 2a + b みたいなことが確かに数学を勉強している時によくありました。
YoutubeやQiitaを見て理解を深める
下記の動画が理解を高めてくれたのと同時に、スタックに関する概念とリスク(オーバーフローを起こすリスク)を説明してくれていました。できるだけ recursive は避けた方が良いのではというのが彼の意見ではありましたので、自分ではなるべく書く必要がないかもしれませんがしっかり理解したいと思います。
実際にひとつひとつ超簡単な例で試す
このドキュメント内の例をもとに理解をしていきました。このようなドキュメントの例を見ても、最初はさっぱり理解できなかったのですが、ひとつ一つ理解を深めていきました。このドキュメント内では、「2 の 3 乗」のような乗数を2つの変数を使った関数をもとに説明しています。
先ほど参考にさせていただいた、Qitia内でも引用されている条件をまずここにも引用します。(独学プログラマーという本の引用だそうです) 再帰関数を理解するための最もシンプルな例 - Qiita
再帰法は、再帰終了条件を持たなければならない。 再帰法は、状態を変えながら再帰終了条件に進んでいかなければならない。 再帰法は、再帰的に関数自身を呼び出さなければならない。
なるほどなるほど。終了条件が必要なのかと理解できます。
function power(base, exponent) { if (exponent == 0) return 1; else return base * power(base, exponent - 1); } console.log(power(2, 3)); // 2の3乗 // → 8
この例から理解すると
if (exponent == 0)
これが終了条件です。power(base, exponent - 1)
この部分が終了条件に向かって進んでいる & 関数自身を呼んでいる
まず一文ずつ理解していきました。で、 2 の 3 乗のケースを一つずつひも解いてきました。
power(2, 3); // base が 2 で、exponent が 3 でそれぞれ代入していきます。
まず、 exponent が 3 なので終了しませんので else
で書かれている return の後が起こります。
2 * power (2, 3-1) なので 2 * power (2, 2) になります。exponent に 2 を入れて power (2,2) をさらに続けます。 私はこの時点で、関数が値であるということがピンときました。値なので、関数が変数のような扱い方がされていていいのだと理解できました。↓続きます
2 * 2 * power (2, 2-1) なので 2 * 2 * power (2, 1) となります。続いて
2 * 2 * 2 * power (2, 0)
2 * 2 * 2 * 1 ← ここで終了条件の exponent == 0 に合致するので、1 が返ってきて終了です。
=> 結局8 となります。
という感じで、リカージョンを理解していきました。
自分でこれを利用し関数を書いてください、と言われたら絶対難しいのですが、書いてあることを理解するレベルにはまずいけました。 パターン化できる、終了条件に向かって自分自身の関数を呼んで進んでいける、ということを書き出せれば理解が進むはずだとわかりました。