はじめに

Recursion の中級で早々に出現する再帰処理に関する項目ですが、再帰関数を使って処理を書くのは初めてだったので正直苦戦しました。

紙を使って書き出したり、コンソールに出力したりする方法も良いですが、今回は Visual Studio Code のデバッガーを使って処理を追う方法を紹介したいと思います。

コールスタックに関数が積み上がっていく様子や、いつベースケースに到達したのか一つ一つ確認できるので理解しやすいと思います。また、連結リストや二分木の学習に進んだときにもコードを理解する手助けになると思うので、余裕があれば是非導入してみると良いと思います。

環境

• OS: Windows11
• 使用エディタ: Visual Studio Code v1.73.1
• Node.js: v18.12.1
• 使用言語: JavaScript

Node.js をインストール

VS Code で Javascript のデバッグを行うために Node.js をインストールします。今回は複数の Node.js のバージョンを切り替えれる nvm をインストールします。

nvm を使用することでシステム内に複数バージョンの Node.js 実行環境をインストールして、指定したバージョンに切り替えるて使用することが出来ます。

インストール方法は以下の記事を参考にして下さい。この記事で執筆時に使用している Node.js のバージョンはv18.12.1です。

デバッガーを実行する

デスクトップ等に適当なフォルダを作成し、index.jsなど適当な JavaScript ファイルを作成し、VS Code で開きます。

ファイル内に以下のコードを貼り付けます。文字列の長さをカウントする再帰関数です。

function lengthOfString(s) {
  // ベースケースが存在しないと、無限ループに陥ります
  if (s === '') {
    return 0;
  }
  return lengthOfString(s.slice(0, -1)) + 1;
}

console.log(lengthOfString('ABCDE'));

サイドメニューの「実行とデバッグ」→「launch.json ファイルを作成します」をクリックして、「デバッガーの選択」でNode.jsを選択します。その後、.vscodeディレクトリ配下にlaunch.jsonというファイルが作成されます。

デフォルトでは下記のような内容で作成されます。もっと詳細な設定に興味がある方はドキュメントを参照してください。

{
  // IntelliSense を使用して利用可能な属性を学べます。
  // 既存の属性の説明をホバーして表示します。
  // 詳細情報は次を確認してください: https://go.microsoft.com/fwlink/?linkid=830387
  "version": "0.2.0",
  "configurations": [
    {
      "type": "node",
      "request": "launch",
      "name": "プログラムの起動",
      // ステップインを飛ばしたいファイル群を指定する
      "skipFiles": [
        // <node_internals>は、Node.jsの内部モジュールを指す
        // この記述をすることで内部モジュールのデバッグの実行がスキップされるようになる
        "<node_internals>/**"
      ],
      // ${workspaceFolder} はVS Codeで開いているフォルダのパス
      "program": "${workspaceFolder}\\index.js"
    }
  ]
}

コードの実行を一時停止したい箇所にブレークポイントを置いて、左サイドメニューの「実行とデバッグ」を選択し、「プログラムの起動」をクリックするかF5キーでコードを実行します。

指定したブレークポイントで実行が一時停止し、その時点での変数の内容や呼び出された関数がコールスタックに格納されていることが分かります。

ベースケースの条件直前まで実行していくと、return lengthOfString(s.slice(0, -1)) + 1;が呼ばれるたびに、変数sの文字列が切り取られていきlengthOfString関数がコールスタックに積み上がっていく様子が見えます。

lengthOfString(s.slice(0, -1)) + 1の+ 1という値はベースケースに到達して値が返ってくるときに加算されていきます。

lengthOfStringメソッドはreturn文で呼び出されているので、ベースケースから戻り値 0 を受け取って値を返したあとは、+ 1を加算して値を返します。コールスタックに積まれた次の関数では、前の関数の戻り値1と+ 1を加算して2を返します。

こうして戻り値を受け取りながら計算し、最終的に5を出力します。

簡単なコードで試していきましたが、総和や階乗でもデバッグを実行してみてください。最初はよく分からなくても、関数が返している値やコールスタックに積まれた関数が実行されるタイミングを見ていると再帰を使った処理も理解できてくると思います。

関数の呼び出しの優先順位

再帰関数の処理の流れを追っていきましたが、演算子には優先順位があります。

関数の呼び出しは四則演算より高いので、関数が呼び出された時点では実行されません。

コールスタックとは？

コールスタックとは呼び出された（実行された）関数が格納されるスタック（Stack）のことです。

Stack とはデータ構造の一種で、最後に挿入したデータが最初に取り出される構造になっています。ここでは深くは触れませんが、詳しくは以下の記事で詳しく説明されていますので興味のある方は読んでみて下さい。

厳密には実行コンテキストが格納されている

先程コールスタックとは、呼び出された（実行された）関数が格納されるスタックだと言いましたが、厳密には実行コンテキスト（関数の場合は関数コンテキストとも呼ばれる）が格納されています。

コンテキストとは「文脈」、「前後関係」などの意味を持ちますが、実行されたコードの情報が格納されています。

つまりどう言うこと？

ざっくり言えば、実行された関数はコールスタックと言うデータ構造に蓄積されて行き、実行が終了するたびにそこから取り除かれるということです。

ここで重要なのはスタックと言うデータ構造を特徴を知っているかどうかだと思います。

最後に

今回は再帰関数はデバッガーを使ったらより理解しやすいよ、ということを解説してきました。

再帰関数に限らず、連結リストなどもデバッガーを使って一歩一歩確認して理解を深めることが重要だと思いました。Visual Studio などは導入も簡単でデバッグ機能も優秀なので、C#で学習を進めるのも良いと思います。