再帰関数を学んでワンランク上のJavaScriptエンジニアになろう！

まえがき

はじめまして！11月入社の新人エンジニアです。
この記事はLivesenseアドベントカレンダーの10日目の記事になります。

本日はJavaScriptを使った再帰関数について書いていきます。どうぞお手柔らかに。

訓示

"なぜ開発言語としてJavaScriptを選ぶのかという問いには、一言で返すことができます。リーチの大きさです" Michael Fogus

想定している読者

• JavaScriptをそこそこ書ける。（スキル判定表で初心者〜中級者くらい？？）
• でももっと高度なJavaScriptが書きたい。
• というか関数型プログラミングに興味がある。

参考図書

この記事を書くにあたって、オライリー・ジャパンの「JavaScriptで学ぶ関数型プログラミング」にお世話になりました。
とても素晴らしい本なので、ぜひ手にとってみることをオススメします。個人的には「開眼！JavaScript」よりも開眼すると思っています。

また、再帰関数の解説に際して、underscore.jsを利用しています。
underscore.jsのメソッドについては適宜説明を入れますので、ご心配なく。

再帰関数とは？

関数が自分自身を呼ぶようなとき、それは再帰関数であると言えます。

再帰関数は複雑なデータ構造の扱いが得意です。

ただしfor文の方が早いことが多いので、使いドコロが限られるかもしれません。それでも、プログラミングの幅が広がるという点では学んでおいて損はないかと思われます。
再帰は関数型プログラミングにおける重要概念の１つであり、ひょっとしたら新しい世界が開けるかもしれません。

JavaScriptで再帰関数を学ぼう！

はじめての再帰関数

では、さっそく再帰関数について学んでいきましょう！まずはシンプルな例から。

配列の要素数を返す関数を定義してみました。

var nums = ['1', '2', '3', '4', '5'];

function arrayLength(array) {
  if(_.isEmpty(array)) {  // isEmpty : 配列要素が空ならtrueを返す
    return 0;
  } else {
    return 1 + arrayLength(_.rest(array)); // rest : 配列から先頭要素を除いた配列を返す
  }
}
arrayLength(nums); // 5

arrayLengthは再帰関数です。処理の中で自分自身を呼んでいます。
また、if文では、終了条件を規定しています。渡された配列が空だった場合に、再帰呼び出しを終了します。

流れを以下に示します。

1. 関数が呼び出される。
2. 配列は空ではないので、else文に入る。
3. 配列の先頭要素を削除して、再度arrayLengthを呼ぶ。

配列が空になるまで2と3の処理が続きます。

もう少し詳しく解説します。
else節のreturn文を見てみましょう。

return 1 + arrayLength(_.rest(array));

returnの内容は、「１＋関数呼び出し」です。
では、関数呼び出しは何を返すのでしょうか？それは、また新たな「１＋関数呼び出し」です。
数学的に代入するとこのようになります。

1 + ( 1 + 関数呼び出し)

そして、配列を使い果たしたとき、if文がtrueになり、0が返されます。

  if(_.isEmpty(array)) {
    return 0; // ←ここに入る。
  } else {
    // 省略
  }

今回の処理におけるreturn文を合算すると以下のようになります。

1 + (1 + (1 + (1 + (1 + (0)))))

配列の要素の数だけ再帰呼び出しが行われます。そして再帰呼び出しの数だけ1が返ります。
結果として、配列の要素数を取得できます。

理解できましたでしょうか？？

別の例を出します。
以下のcycle関数は、引数で与えられた数だけ、配列の中身を表示します。

var langs = ['Java', 'Ruby', 'Python'];

function cycle(times, array) {
  if(times <= 0) {
    return [];
  } else {
    console.log(array);
    return cycle(times - 1, array);
  }
}
cycle(3, langs); // [ 'Java', 'Ruby', 'Python', 'Java', 'Ruby', 'Python', 'Java', 'Ruby', 'Python' ]

timesを消費して再帰が行われています。

また、再帰関数にはいくつかの種類があります。以下で例を示します。

相互再帰関数

相互再帰関数について解説します。
２つ以上の関数が互いを呼び合うのが相互再帰関数です。

function isEven(n) {
  if(n === 0) {
    return true;
  } else {
    return isOdd(Math.abs(n) - 1);
  }
}

function isOdd(n) {
  if(n === 0) {
    return false;
  } else {
    return isEven(Math.abs(n) - 1);
  }
}

isEven(11); // false
isOdd(11); // true

上記は、奇数か偶数かを判定する関数であり、互いを呼び合っています。
これが相互再帰関数です。

ただし、これらの関数は実用性に欠きます。配列の要素数なら、array.lengthで取得できますもんね。
これより後で実用的な再帰関数を定義します。

ファイル検索関数

ファイル構造への操作は、再帰関数にピッタリです。

まずは、以下のようなデータを用意します。これは擬似的なファイル構造を表します。

var files = {
  'Desktop' : [ 'index.html', 'main.js', 'myDog.jpg' ]
  ,
  'Downlod' : [ 'underscore.min.js', 'something.zip' ]
  ,
  'JSPractise' : [ 'rect.js', {
        'reactPractise' : ['react01.js', 'react02.js', 'react03,js', {
            'todoList' : ['todo.html', 'todo.slim', 'todo.js']
          }
        ]
        ,
        'nodePractise' : [ 'node01.js', 'node02.js' ]
      }
    ]
};

オブジェクトの各要素が１つ１つのディレクトリを表します。keyがディレクトリ名で、valueが直下の要素ですね。
valueの中にはさらにオブジェクトが格納されている場合があります。これはさらなるサブディレクトリを表します。

今回は、todo.slimというファイルを探して、そこに至るまでのパスを表示させてみましょう。

以下にファイル検索を行う関数を記述しました。

// 今回は「文字列である＝ファイルである」と定義
function isFile(name) {
  return _.isString(name); // isString : 引数のデータが文字列ならばtrueを返す。
}

// lookDir関数は１階層とその下の階層を走査
function lookDir(dirs, file, path) {
  var path = path || '';
  _.each(dirs, function(dir, dirName) {
    _.each(dir, function(child){
      if(isFile(child)) {
        if(child === file) {
          console.log(path + dirName + '/' + child);
        }
      } else {
        lookDir(child, file, path += dirName + '/');
      }
    });
  });
}

複雑に見えますが、処理内容はシンプルです。一緒に見ていきましょう。

まずlookDir関数の定義について。

// lookDir関数は１階層とその下の階層を走査
function lookDir(dirs, file, path) {

この関数はある階層と、その１つ下の階層をチェックします。コメントに書いてあるとおりですね。
引数としては、３つの引数を取ります。

• dirs : １つの階層全体
• file : 検索対象のファイル名
• path : ファイルに至るまでのパス

以上です。それぞれがどう使われるのかは、追って見ていきましょう。

次に、変数定義について。

var path = path || '';

pathという変数を定義しています。
OR演算子を使っているのは、初回呼び出し対策です。初回ではpathは未定義です。この関数では引数を２つだけ受け取ると想定しています。pathは内部的に生成される変数なのです。
そのため、初回では''が代入され、次回以降の再帰呼び出しでは、引き継がれたpathが代入されます。

次に、メインとなるループ処理について見ていきます。

_.each(dirs, function(dir, dirName) {
    _.each(dir, function(child){

ややこしそうに見えますが、単なる２重ループです。
外側のループがディレクトリを対象にしており、内側のループがそれぞれの子要素を対象にします。
つまり、外側が「Desktop→Download→JSPractise」とループし、内側が「index.html→main.js→myDog.jpg」のようにループします。

そして、肝心の処理内容がこちら。

if(isFile(child)) {
    // 後述
} else {
    // 後述
}

ここでようやく、ファイル検索を行っています。
if文は対象がファイルであるかどうかをチェックします。なぜなら、対象は「ディレクトリの子要素」であり、それがファイルなのかサブディレクトリなのかはまだ分からないからです。

対象がファイルであった場合、以下の処理が走ります。

if(child === file) {
    console.log(path + dirName + '/' + child);
}

そのファイルが検索対象かどうかチェックします。そして検索対象であったなら、パスを表示します。
文字列結合の中身は以下のとおり。

• path : このディレクトリにたどりつくまでのパス
• dirName : 今回チェック対象となったディレクトリ名（Desktop, Downlodなど）
• child : 今回チェック対象となったファイル名（index.html, main.jsなど）
  　

一方で、チェック対象がファイルではなくディレクトリだった場合は再帰呼び出しを行います。

lookDir(child, file, path += dirName + '/');

その際に引数として、３つのものを渡します。

• child : サブディレクトリ
• file : 検索ファイル名
• path += dirName + '/' : ここまでのパスに、今回チェック対象となったディレクトリ名とスラッシュを結合したもの

ここで分かるように、fileという変数はただの文字列渡しであり、中身が変わることはありません。

以上でファイル検索関数の解説はおしまいです。
実際に関数を実行してみましょう！

lookDir(files, 'todo.slim');

ローカルで実行した結果がこちら！

きちんとパスが表示されています。再帰すごい！

あとがき

手短ですが、再帰関数について見てきました。いかがでしたか？
再帰のすごいところは、呼び出しの深さが自由なところですね。先ほどの例では、もっと深いファイル構造でも問題なく動きます。

それではみなさんのJavaScriptライフがより素敵なものになりますように！

if ( 再帰を理解できた！たのしい！) {
　あしたはEtsさんの記事です。
} else {
JavaScriptで再帰関数を学ぼう！
}