エンジニアへの道　No10

再帰

---

再帰の意味、目的：　

• 再帰はある関数の中で同じ関数を実行し、それにより処理を自動化するためのプロセス。

再帰のキーワード：

• ベースケース : 再帰関数において、ループの終了させるための宣言のこと。

• 再帰呼び出し (Recursive call): 関数内で自身の関数を呼び出すこと。再帰呼び出しにより、問題が小さな部分問題に分割される。

• 再帰的な処理 (Recursive process): 再帰関数によって問題が分割され、小さな部分問題が解決される過程。

• 再帰的な性質 (Recursive nature): 問題が自身の中で同じ問題を解決するために再帰的に定義される性質。例えば、階乗やフィボナッチ数列などが再帰的な性質を持つ。

例えば、７の倍数を再帰化してみます。
通常、7 *1 , 7 * 2, 7 * 3……と、計算しますが、再帰化してみると
7 + ７をしたあとその足した数（この場合、14）に７をまた足すを繰り返しています。これをコード化するだけです。

再帰化関数の例

---

multiple7という関数の中にnという自然数を引数とした関数があるとします。それでは、実際に再帰化してみます。

function multiple7(n){
  //ベースケースの宣言
　　if(n <= 0){
      return 0;
      }

　　//再帰化
　　//7 * n を　7(n-1)と書き換え
　　//最後に新たな7を足す
　　return multiple7(n-1) +7;
　}

この関数で表しているのが

1. まずは、上からベースケースの宣言。　この場合、nの自然数が0以下になった場合、この関数の処理を終了と宣言しています。

2. ここで、再帰関数の登場です。　なぜ、7 *nが7(n-1) + 7になるのかというと

例えば、nの引数に3を入れて見ましょう。
7 * 3 = 21となりますよね、
再帰化の場合、目的として同じ関数の中で自分自身を実行し、処理の自動化をすることでした。

そこで、
multiple7(3) とすると、multiple7(2) + 7 となります。
「　7 * (3 - 1)　」ここで 7 * 2となり　かっこ外の「　+ 7 　」が
　
その後に計算されて結果、21となる。そしてこの処理を繰り返していき、
nの引数が０になったら処理を終了します。

再帰関数の例２

---

文字列の逆表示を再帰関数で処理する。 まず、文字列の後ろから 1 文字ずつ切り取っていく処理を考えます。substring 関数を使って、substring（文字列 - 1）で最後の1文字を切り取ることができます。例えば、"abcd"の場合、

function reverseString(s){ 

// ベースケース if (s.length <= 1) return s;

 // substring関数を使って最後の1文字を切り取ります。 
let subStr = s.substring(0, s.length - 1); return s[s.length - 1] + reverseString(subStr); } 

console.log(reverseString("abcd"));

1. ベースケースでは、与えられた文字列 s の長さが1以下の場合、そのままの文字列を返します。

2. それ以外の場合、与えられた文字列 s の最後の1文字を取り出し、その文字を先頭に置いた文字列を返すとともに、残りの文字列に対して同じ操作を再帰的に行います。

3. 再帰呼び出しがベースケースに達するまで、文字列を1文字ずつ取り出して、それを逆さまにしていきます。

こうして、文字が逆さまになる再帰関数が作成できました。

最後に

---

このように再帰関数により、簡潔に処理の内容を理解することができる関数になります。実際、今の理解度は半々な感じなのでこれからも再帰関数は使うことになっていくので引き続き学んでいこうと思います。