再帰、、、それはやりたいことは簡単なのに、コードを書こうとすると頭を混乱させる悲しいもの。私自身、再帰（Recursion）を学習したとき、すとんと来るまで時間がかかりましたが、いくつかのパターンに分けて理解すると、すっきりと分かりやすかったのでシェアします！
0. 基本形
1 function 関数名（引数）｛
2 if (終わりの条件）｛
3 終わったときのリターン文
4 }
5 それ以外のときの処理
6 リターン文（この中でこの関数自体を使う＝再帰的）
7 ｝
2～3行目：延々と再帰しないように、まず、終わりの条件と終わるときのリターン文を書く。ここを「ベースケース」と呼ぶ。
5～6行目：続いて、それ以外の処理を書き、リターン文を書くがここで、定義しているこの関数自体を使うので、また関数の頭に戻って、ぐるぐる回る、これが「再帰的」。
ベースケース中のreturnは直感的に必要と分かるでしょうが、最終的に返すのはここだからと、6行目のreturnを書かないと、最初に渡す引数がベースケースに相当する場合しか、値が返ってきません。
また、再帰して、何サイクルも関数が繰り返されるとき、そのサイクルごとの戻り値が、前のサイクルに流れない。（と、うまく伝わるでしょうか。表現が難しいので、以下のパターン中の図をご覧ください。）
1. 「引数」と「引数を変化させてその関数自体に渡したもの」を計算するパターン
なんのこっちゃ？ 言葉で表現するのが難しいので、下の例の5行目をご覧ください。
例：引数nの階乗を求める関数。
1 function factorial(num){
2 if (num===0||num===1){
3 return 1;
4 }
5 return num * factorial(num-1);
6 }
このケースではreturn num * factorial(num-1)と、最初の引数に、その引数を変化させたものを新たな引数として同じ関数に渡したものを、掛け合わせています。
例えば、5を引数にしてfactorial(5)とすると、5行目で5 * factorial(4)を返す。
このfactorial(4)は、5行目で4 * factorial(3)を返し、
そのfactorial(3)は、5行目で3 * factorial(2)を返し、
そのfactorial(2)は、5行目で2 * factorial(1)を返し、
そのfactorial(1)は、3行目で1を返す。 . . . となります。
図に書くと
return 5 * factorial(4)
↑
return 4 * factorial(3)
↑
return 3 * factorial(2)
↑
return 2 * factorial(1)
↑
return 1 ⇐ベースケースで止まり！
ベースケースで止まった時に１が確定。そして後ろからどんどん戻り値が返されて、最終的に 5 * 4 * 3 * 2 * 1 が返されます。
2．引数自体を変化させていくパターン
例：要素が1つになるまで配列の要素を足し合わせて、できた配列を返す関数。
1 function reduceArray(array){
2 if(array.length === 1){
3 return array;
4 }
5 array[1] = array[0] + array[1];
6 array.shift();
7 return reduceArray(array);
8 }
ここで例えば[1, 3, 5, 7]という配列を引数として渡してreduceArray([1, 3, 5, 7])とすると、
これは、5，6行目でarrayを変化させ、7行目でreduceArray([4, 5, 7])を返す。
そのreduceArray([4, 5, 7])は、同様にarrayを変化させ、reduceArray([9, 7])を返す。
そのreduceArray([9, 7])は、同様にarrayを変化させ、return reduceArray([16])を返す。
そのreduceArray([16])は、16を返す。
図に書くと
reduceArray([1, 3, 5, 7])
↑
return reduceArray([4, 5, 7])
↑
return reduceArray([9, 7])
↑
return reduceArray([16])
↑
return 16 ⇐ベースケースで止まり！
やはり、ベースケースで止まったところで、16という値が確定。これが後ろからどんどん戻されて、最終的にreduceArray([1,3,5,7])は16を返します。
3. 引数を変化させつつ、答として返す別の値を設けて、そちらを変化させていくパターン。
このパターンでは、答として返す別の値を関数の本体の中で宣言するのではなく、第二引数としてデフォルト値をつけて設けます。これによって、関数が繰り返されるとき、この値が初期化されてしまうのをうまく避けられます。
例：数nから0まで1ずつ減らした整数を足した値を返す関数。nが5なら5+4+3+2+1を返す関数です。
1 function addNum(num, result = 0){
2 if (num === 0){
3 return result;
4 }
5 result += num;
6 num --;
7 return addNum(num, result)
8 }
例えば、3を引数に渡してaddNum(3)とすると、第二引数がない場合はデフフォルトが使われるのでaddNum(3, 0)と同じ。5行目でresult、6行目でnumを変化させ、7行目でaddNum(2, 3)を返す。
そのaddNum(2, 3)は、同様にresultとnumを変化させ、7行目でaddNum(1, 5)を返す。
そのaddNum(1, 5)は、同様にresultとnumを変化させ、7行目でaddNum(0, 6)を返す。
そのaddNum(0, 6)は、3行目で6を返す。
図に書くと
addNum(3) ⇒ addNum(3, 0)
↑
return addNum(2, 3)
↑
return addNum(1, 5)
↑
return addNum(0, 6)
↑
return 6 ⇐ベースケースで止まり！
こちらもベースケースで止まって6が確定。これが後ろから戻され、addNum(3)は6を返します。
4. returnを忘れずに。
最初に書いたように、ベースケースだけでなく、ベースケース以外の処理のときのreturnも必要です。
もちろん、最終的な値を返すという役割もありますが、このreturnのおかげで、上の３つの図にあるように、後のサイクルの戻り値が、前のサイクルに返されます。言い換えれば、returnがないと、関数は実行されていても、後のサイクルの戻り値がどこにも行かずじまいになってしまいます。
とても分かりやすい動画はこちら：Best Javascript Recursion Explanation on YouTube