[プログラミング]再帰関数となかよくなろう数列と再帰関数

どうも。つじけ（tsujikenzo）です。このシリーズでは、「再帰関数となかよくなろう」をお届けします。今日は1回目で、「数列と再帰関数」をお届けします。

はじめに

これまで、繰り返し処理をおこなう方法として、for文やwhile文などの、制御構文をまなんできました。

プログラミングには、for文やwhile文より強力な、再帰関数という手法があります。

繰り返し処理をラクに書く手法ですので、ぜひ、なかよくなってみましょう。

今日のアジェンダ

再帰関数とは
再帰関数とメモリ
数列の再帰関数のプログラミング

再帰関数とは

再帰呼び出し

再帰呼び出しとは、ある関数Xから、関数X自身を呼び出すことです。

ただし、このままだと無限ループになってしまい、最終的にエラーになってしまいます。

ベースケース

無限ループを終了させるために、関数内に書かれた条件処理を、ベースケースといいます。

ベースケースがないと、無限ループになります。

再帰ステップ

再帰呼び出しを行い、その結果を用いて行う処理を、再帰ステップといいます。

再帰呼び出しに渡される引数は、最終的にベースケースで処理されるように、書かなければなりません。

つまり、再帰関数とは、「再帰ステップで、再帰呼び出しをループすると、必ずベースケースに到達する」 ということになります。

演習1

3 + 2 + 1 = 6 です。（解説は後ほど）

再帰関数とメモリ

「関数のなかで関数自身を呼び出す」と聞くと、混乱してしまうひともいるでしょう。現実世界では「ある部品がその部品を使って作られている」ということは考えにくいからです。

そのようなときは、メモリの動きで、再帰関数を理解してみましょう。

スタック領域

プログラミングでは、ソースコードを実行すると、メモリ上にコピーを作成します。

関数や引数がコピーされるメモリ上の領域のことを、スタック領域といいます。

関数は呼び出されるたびに、関数のコピーをスタック領域に作成します。

スタックフレーム

呼び出された1つ1つの関数を、スタックフレームといいます。

スタックフレームは、引数や戻り値などをもつこともできます。

また、呼ばれた関数はスタックフレームとして上から積み重ね、使い終わったスタックフレーム（関数が処理を抜けるなど）は、スタック領域から捨てられます。

引数や戻り値は、スタックフレームが積まれるさいや、捨てられる際、次のスタックフレームに渡すこともできます。

演習2

コールスタックを開いて、スタックフレームが積まれていることを確認しましょう。

再帰関数とスタックフレーム

再帰関数も同じように、関数が呼び出されるたびに、スタックフレームが積まれていきます。

再帰呼び出しでは、関数はスタックフレームA、B、Cという風に、別の関数として呼び出されていると考えるといいでしょう。

また、その際に、引数を渡すことで、次のスタックフレームに処理をお願いするというイメージです。

もちろん、このままでは無限ループになってしまいますので、ベースケース（（n<0）returnなど）を設置して、処理が終わるような設計をしなければなりません。

数列と再帰関数

数列とは、「数が列になったもの」です。数が置かれる場所を「項」といいます。

また、項の場所は添字（インデックス）で表現します。

一般化

添字には、変数nを使うことが多いので、数列のn番目という表現を使います。

変数nを使って、数列を表現すること、一般化といいます。

上記の数列A、数列Bを、それぞれ一般化してみましょう。

数列Aのnは、n-1 + 2と表現できます。数列Bのnはn2（nの二乗）と表現できます。

数列の前後の値をみて一般化するコツは、3パターン＋特殊パターンを覚えることです。

まずは、前後の値を割ったり引いたりして、結果を考察してみましょう。

演習3

漸化式

数列Aのn番目の値は、n-1 + 2でした。

このように、各項を、それ以前の項の関数であらわした関係式を、漸化式（ぜんかしき）といいます。

n番目の値を、n-1番目の値を使って表現できないか、ということを考えるのがポイントです。

数列Bのn番目の値は、n2(nの二乗)でした。

しかし、f(n)を、f(n-1)であらわすと、f(n) = f(n-1) + 2n – 1 ともいえます。

演習4

漸化式では、「それ以前の項の関数」を、再帰的に呼び出しています。

この再帰的な関数の呼び出しは、プログラミングでラクに書くことができます。

数列の再帰関数のプログラミング

数列の再帰関数のプログラミング手順を、以下にまとめました。

例題として『1～10の総和を求める問題』を、プログラミングしてみましょう。

まず、具体的な数値で値を求めます。

f(1)のとき・・・1
f(2)のとき・・・3
f(3)のとき・・・6
//中略
f(10)のとき・・・55

f(n)のときを、変数nを使って一般化します。

f(n)のとき・・・f(n-1) + n

漸化式ができました。

f(n) = f(n-1) + n

引数、戻り値、処理内容を確認します。

引数・・・自然数の1～10
戻り値・・・直前の項の値に、今の引数を足したもの
処理内容・・・直前の項の値を計算する

ソースコードを書きます。まず、再帰ステップを実装します。

再帰ステップでは、まず以前の項の値を変数に格納します。

//再帰ステップ
const sum = func(n-1);

そして、変数に変更を加えたものを、戻り値にします。

//再帰ステップ
const sum = func(n-1);
return sum + n ;

このままでは、無限ループしてしまいますので、ベースケースを実装します。

今回は、10,9,8,7…3,2,1,0ということで、nが0になったときは、0を返して関数をreturnさせます。

//ベースケース
if(n === 0) return 0;

関数化（アロー関数）して、呼び出せば、完成です。関数名もわかりやすく変更しました。

function myfunction5() {

  /**
   * 自然数1～nまでの総和をもとめる関数
   * @param {number} n
   * @return {number} 総和
   */
　　const getSum = n => {

    //ベースケース
　　if (n === 0) return 0;

    //再帰ステップ
　　const sum = getSum(n - 1);
    return sum + n;
  }

  console.log(getSum(10));　//55
}