JavaScript、再起関数とは?

自分を呼び出している関数。

こんにちは、「ふ」です。
今回は「再起関数」というものを学習しましょう。

function a() { console.log("AAA"); } function b() { a(); }

⬆︎のサンプルをみてください。
関数bが内部で関数aを呼び出していますね。 これはフツーに見られるものです。

function c(n) { return c(n-1); }

では⬆︎はどうでしょう。
関数cが内部で自分自身（関数c）を呼び出しています。

自分を呼び出している？

そうです。再起関数とは、「関数の中で自分自身を呼び出している関数」のことを呼びます。
初めて目にした方は、関数が自分自身を呼び出すことができることに驚いた！のではないでしょうか。JavaScriptの関数ではそれが可能なのです。




扨（さて）この不思議な再帰関数、

・どういうプロセスになっているのか？
・どういう役割を持つのか？？
・作り方の注意点は？？？
・再帰関数を使うメリットは？？？？？
・習得するにはどうすれば....

について、詳しく紹介していきたいと思います。


また「再起関数、一度ぼんやりと学習したことはあるが、いまいち自分で使うとなると....」

な方も、当ページではそのプロセスを一切省略することなく、じっくり掘り下げてお話ししていきますので、再起関数を「自分のもの」となるよう、改めて学習していきましょう。

基本サンプル。

再帰関数のとてもシンプルなサンプルをあげてみます。

function m(n) { if(n<=1) ｛ bbreturn n; ｝ else ｛ bbreturn n + m(n-1); bb｝ }

この関数mですが、中で条件分岐がされています。
もし引数nが１以下なら、nそのものを返します。そうでなければ、引数nに「n-1」を引数とした自身の関数を加算したものをreturn。

console.log(m(3)); 「「３// ▶︎ 6」」 console.log(m(10)); 「「３// ▶︎ 55」」

関数mを実行してみると、１から引数までの整数の合計が出力されました。
このことから考えるに、どうやらループ処理のようなものが行われている模様です。

これは....どうなってしまっているのか💧
大丈夫です。プロセスを事細かに見ていけば、単純な処理の繰り返しであることがわかります。

プロセス。

m(3);

それではm(3)を実行したときのプロセスをじっくりと観察しましょう。

m(3)の内容が上から順に実行されていきます。
最初のif文にある条件。引数３に対してこれはfalseなので、ここの処理はスルーされますね。

そしてif文の条件に当てはまらなかったので、elseの処理が行われます。
処理内容は、

return n+m(n-1);

「引数３と、『n-1』を引数とした自身の関数mを足したものをreturnする」

となっているので、
その値を得るには「『n-1』を引数とした自身の関数m」、つまりm(2)を呼び出して返り値をもらってくる必要があります。

そのため、ここでm(2)が呼び出されます。

m(2)が呼び出されて、その処理が始まりました。
m(3)のときと同じく、最初のif文の条件に対してはfalseです。よってスルー。

elseの処理に移ります。

「現在の引数nは『２』。これと『n-1』を引数とした自身の関数mを足したものをreturnする」

なので、返り値を得るためにm(n-1)、つまりm(1)を呼び出すことになります。

m(1)が実行されます....が、ここでの処理はこれまでとは違います。

引数nは「１」なので、if文の条件である「n<=1」はtrueとなります。従ってtrueの処理であるn（現在は「1」)をreturnします。

returnしたので、else以降の処理はされることなく関数m(1)は終了します。

returnしたnの値「１」はどこに返されるのでしょうか？
〜それはn(1)を呼び出したn(2)のelseの部分です。

m(1)の返り値「1」は、そもそも呼び出したm(2)のreturn処理にあるm(n-1)の部分に渡されます。

関数m(2)はm(n-1)の返り値を得たので、これで晴れて「n+m(n-1)」をreturnすることができます。
m(2)において、引数nは「2」、m(n-1)の値も「1」です。
従って返り値「3」をreturnし、returnしたので関数m(2)も終了します。

m(2)の返り値は、呼び出し先であるm(3)のelse処理、その中にあるm(n-1)に返されます。

そしてようやく、最初のm(3)もm(n-1)の返り値を得て、「n+m(n-1)」をreturnできるようになりました。
m(2)での返り値は「3」、m(3)における引数nは「3」なので、返り値「6」をreturnして、元々の関数であったm(3)も終了です。

再起関数の正体。

これまでの流れを、全体的なところで見てみましょう。
再起関数の正体が見えてきます。

関数が内部で自分自身の関数を呼び出すことを、再帰呼び出しと言います。
前半戦は、if文の条件である「n <= 1」がfalseである限り、再帰呼び出しを続けます。条件がtrueとなったところでストップ。

trueになったら、そこから１つ前の関数にreturn値を渡して、末端の関数から順次終了していきます。
最終的にそもそもの関数であったm(3)がreturn値を返し、一連の流れが完結します。

それでは各関数がreturnの際、実際に行った処理はどうなのか。

末端の関数であるm(1)が「1」を返し、m(2)は「2+1」を返し、m(3)は「3+2+1」を返していることになります。
つまるところ関数m(n)は、「1〜nの整数を順に加算していく」というループ処理のような仕事をしていることになります。



JavaScriptにはfor文やwhile文などのループ処理があらかじめ用意されていますが、再帰関数はループ処理を自作している、といったところです。

必要な２つの構成。

再起関数を実装する際には２つの構成が最低限必要です。

　1.再帰呼び出し停止条件とその処理
　2.終了条件にたどり着くようにする

1.再帰呼び出しの停止条件とその処理。

先のセクションで述べたように再起関数は「自作のループ処理」であるため、再起呼び出しの停止条件とその時の処理を用意する必要があります。

function a(b) { return a(b-1); }

この⬆︎関数は再帰呼び出しの停止条件を用意していないため、実行すると永遠に再帰呼び出しを繰り返してしまいます。

a(5); 「「３// ▶︎ maximum call stack size exceeded」」

consoleに「最大呼び出しスタックサイズを超えました」とエラーが出ます。

function a(b) { if「「１(b<1)」」 ｛ bb「「５return;」」 ｝ else ｛ bbreturn a(b-1); bb｝ }

「bが1より小さい場合」という条件を加えました。返り値を必要としなければreturnのみで終了させても差し支えありません。

2.終了条件にたどり着くようにする。

1.の再起呼び出しの停止処理とともに、elseの処理は最終的にif条件がtrueになるようにしなくてはいけません。

function a(b) { if(b<1) ｛ bbreturn; ｝ else ｛ bbreturn 「「１a(b-1)」」; bb｝ }

⬆︎の関数aはOKです。
引数に正の整数を与えた場合、a(b-1)の再起呼び出しが繰り返されて、いずれはa(1)にたどり着きます。

function c(d) { if(d<1) ｛ bbreturn; ｝ else ｛ bbreturn 「「４c(d+1)」」; bb｝ }

一方こちらはよろしくありません。
再帰呼び出しのたびに引数dに１が加算されていくため、いつまでたっても停止条件である「d<1」にたどり着くことができません。この関数cも実行するとオーバーフローを起こしてしまいます。

function sample(「「１引数」」) { if(「「５終了条件」」) ｛ bbbbreturn 〇〇; bb｝ else ｛ bbbbreturn sample(「「５終了条件」」に向かっていく「「１引数」」を含める); bb｝ }

1.2.の構成を踏まえた形で再起関数を実装するようにしましょう。

再起関数のメリット。

ここまで再起関数の内容を見てきましたが、そのメリットはどこにあるのでしょうか？
フツーにfor文を使ったほうが手っ取り早いのでは？と思うことでしょう。

再起関数を使うことのメリットの１つは、記述の短縮です。

function m(n) { if(n<=0) ｛ bbreturn n; ｝ else ｛ bbreturn n+m(n-1); bb｝ }

先にサンプルとして取り上げた、１〜nの整数を加算していく関数mです。
詳しいプロセスを説明するためにif文を使って表記していましたが、これを条件演算子を使って記述してみます。

function m(n) { return (n<=1)? n : n+m(n-1); }

なんと！
長ったらしい内容が１行で書けてしまいました。もちろんfor文よりも短くて済みます。

そして、初心者っぽくない見た目のコードになりましたね。これもメリットの１つとしてあげておきましょう（笑）

その他、アルゴリズムによっては再起関数を使ったほうが有利な場合も多々あるようです。
その辺については「ふ」も調査中（←というか勉強不足）なので、機が熟したら紹介させていただきます。

条件演算子、くわしくはこちら⬇︎

JavaScriptのはてな「?」とコロン「:」〜条件演算子について。

2022.01.18
if文の代わりになるのか?

自分のものにするために。

再起関数を自分で使いこなせるようになるためには、以下の２つが有効です。

簡単なループ処理を書いてみる。

これまでfor文やwhile文で記述していたものを、再帰関数で表現してみてください。自分で作ってみるのが習得への最短ルートとなります。

例えば

　「"hello"をn回、console.logする」

などといった、超シンプルなものから始めると良いでしょう。

プロセスを分解する。

再起関数を学習中。
サイトなどのサンプルコードを見て「???」となったとき。
当記事の「プロセス」のセクションに習って１つ１つの処理を事細かに分解してみてください。

そうすれば「このコードは何をやっているのか」が判明するはずです。

最後までお読みくださり、ありがとうございました。
この記事がもし、プログラミング学習を頑張っているあなたの手助けとなれば、「ふ」はとっても嬉しく思います。

今後もJavaScriptのハマりどころに関する調査・発信を続けていきますので、web上で見かけたときはぜひお立ち寄りください。

ではまた〜 ♫