JavaScript Programming

関数の使い方

今回は関数の基本的な使い方について説明します。JavaScript は柔軟なプログラミング言語なので、無理にオブジェクト指向機能を使わなくても、いろいろなプログラムを作ることができます。このとき、なくてはならない機能が関数です。関数を使いこなすことができるようになると、ちょっと複雑なプログラムでも簡単に作ることができます。

●関数定義

関数を定義するときは function 文を使います。簡単な例として、数を 2 乗する関数を作ってみましょう。次のリストを見てください。

リスト : 数を 2 乗する関数

function square(x) {
    return x * x;
}

function 文の構文を下図に示します。function 文は図のように数式と比較するとわかりやすいでしょう。

function 名前(仮引数名, ...) {
    処理A;
    処理B;
    ...;
}

図 : JavaScript の関数定義

それでは実際に実行してみます。

> function square(x) { return x * x; }
undefined
> square(10)
100

関数を定義するには名前が必要です。function 文の次に関数の名前を記述します。JavaScript の場合、function 文で定義された処理内容は、名前で指定した変数に格納されます。

関数名の次にカッコで引数名を指定します。引数を取らない関数は () と記述します。JavaScript の場合、カッコを省略することはできません。それから、関数定義で使用する引数のことを「仮引数」、実際に与えられる引数を「実引数」といいます。 square の定義で使用した x が仮引数で、square(10) の 10 が実引数となります。

そして、カッコの後ろのブロックの中で処理内容を記述します。square() の処理は return x * x; の一つだけですが、ブロックの中では複数の処理を記述することができます。JavaScript の場合、関数の返り値は return 文を使って返します。これはＣ言語と同じです。Perl のように、ブロックの最後で実行された処理結果が返り値とはなりません。return のない関数、または return に引数がない場合は undefined を返します。

●ローカル変数とグローバル変数

それでは、ここで変数 x に値が代入されている場合を考えてみましょう。次の例を見てください。

> x = 5
5
> square(10)
?

結果はどうなると思いますか。x には 5 がセットされているので 5 の 2 乗の 25 になるのでしょうか。これは 10 の 2 乗が計算されて、結果は 100 になります。そして、square() を実行したあとでも変数 x の値は変わりません。

> square(10)
100
> x
5

square() の仮引数 x は、その関数が実行されている間だけ有効です。このような変数を「ローカル変数 (local variable) 」もしくは「局所変数」といいます。これに対し、 最初に変数 x に値を代入した場合、その値は一時的なものではなく、その値は JavaScript を実行している間ずっと存在しています。このような変数を「グローバル変数 (golbal variable)」もしくは「大域変数」といいます。

JavaScript は変数の値を求めるとき、それがローカル変数であればその値を使います。ローカル変数でなければ、グローバル変数の値を使います。次の例を見てください。

> x = 10
10
> y = 20
20
> function foo(x){ console.log(x); console.log(y); }
undefined
> foo(100)
100
20

最初にグローバル変数として x と y に値を代入します。関数 foo() は仮引数として x を使います。foo() を実行すると、x はローカル変数なので値は実引数の 100 になります。y はローカル変数ではないのでグローバル変数の値 20 になります。下図を見てください。

このように、関数内ではローカル変数の値を優先します。プログラムを作る場合、関数を部品のように使います。ある関数を呼び出す場合、いままで使っていた変数の値が勝手に書き換えられると、呼び出す方が困ってしまいます。部品であるならば、ほかの処理に影響を及ぼさないように、自分自身の中で処理を完結させることが望ましいのです。これを実現するための必須機能がローカル変数なのです。

●ローカル変数の定義と有効範囲

JavaScript の場合、関数の引数はローカル変数になりますが、var で宣言した変数もローカル変数になります。

var 変数1, ..., 変数N;
var 変数1 = 値1, ..., 変数N = 値N;

簡単な例を示しましょう。

リスト : 要素の合計値を求める

function sum(ary) {
    var total = 0;
    for (var i = 0; i < ary.length; i++) {
        total += ary[i];
    }
    return total;
}

関数 sum の引数 ary には要素が数値の配列を渡します。変数 total は var で宣言されているのでローカル変数になります。for 文で使う変数 i も var で宣言されているのでローカル変数になります。sum() の処理内容は簡単です。最初に、変数 total を0 に初期化します。次に、for 文でリストの要素を順番に取り出して total に加算していきます。最後に return で total の値を返します。実際に実行すると次のようになります。

> sum([1, 2, 3, 4, 5])
15

ローカル変数が値を保持する期間のことを、変数の「有効範囲 (scope : スコープ) 」といいます。JavaScript の場合、引数を含む関数内のローカル変数は、関数を実行している間だけ有効です。関数の実行が終了すると、これらの変数は廃棄されます。

Ｃ言語や Perl に慣れているユーザにとって、JavaScript のスコープはちょっとわかりにくいかもしれません。Ｃ言語や Perl の場合、ブロックごとにローカル変数の有効範囲を設定できますが、JavaScript にはできません。JavaScript は関数単位でローカル変数の有効範囲を管理しています。なお、ECMAScript2015 では変数を let / const で宣言すると、ブロック単位で変数の有効範囲を管理できるようになります。

●可変個引数

JavaScript の関数はちょっといい加減なところがあって、引数の個数をチェックしていません。つまり、仮引数の個数と実引数の個数が合わなくてもエラーにはならないのです。仮引数よりも実引数の個数が少ない場合、余った仮引数には undefined がセットされます。逆に、仮引数の個数が少ない場合、余った実引数は捨てられるのでしょうか。実はそうではなく、関数に渡された引数はローカル変数 arguments に格納されています。

簡単な例を示しましょう。

> function foo() { for (var i = 0; i < arguments.length; i++) console.log(arguments[i]); }
undefined
> foo(1, 2, 3)
1
2
3

foo(1, 2, 3) と呼び出した場合、実引数 1, 2, 3, はそれぞれ arguments[0], arguments[1], arguments[2] にセットされます。このように、arguments を使うと可変個引数の関数を定義することができます。というよりも、JavaScript は可変個引数の関数がデフォルトと考えた方がよさそうです。

●データの探索

それでは簡単な例題として、データの探索処理を作ってみましょう。データの探索とは、あるデータの中から特定のデータを見つける処理のことです。データの探索はプログラムの中で最も基本的な操作のひとつです。ここでは配列の中からデータを探すことを考えます。

いちばん簡単な方法は先頭から順番にデータを比較していくことです。これを「線形探索 (linear searching) 」といます。たとえば、配列の中からデータを探す処理は次のようになります。

リスト : データの探索

function find(n, ary){
    for (var i = 0; i < ary.length; i++) {
        if (n == ary[i]) return true;
    }
    return false;
}

関数 find() は配列 ary の中から引数 n と等しいデータを探します。for 文で配列の要素を一つずつ順番にアクセスして n と比較します。等しい場合は true を返します。n と等しい要素が見つからない場合、for ループを終了して false を返します。

見つけた要素の位置が必要な場合は次のようになります。

リスト : 位置を返す

function position(n, ary){
    for (var i = 0; i < ary.length; i++) {
        if (n == ary[i]) return i;
    }
    return -1;
}

関数 position() は等しいデータを見つけた場合はその位置 i を返し、見つからない場合は -1 を返します。

find() と position() は最初に見つけた要素とその位置を返しますが、同じ要素が配列に複数個あるかもしれません。そこで、要素の個数を数える関数を作ってみましょう。次のリストを見てください。

リスト : 個数を返す

function count(n, ary) {
    var c = 0;
    for (var i = 0; i < ary.length; i++) {
        if (n == ary[i]) c++;
    }
    return c;
}

変数 c を 0 に初期化し、n と等しい要素 x を見つけたら c の値を +1 します。最後に return で c の値を返します。

それでは実際に試してみましょう。

> a = [1,2,3,4,5,1,3,5,3]
[1, 2, 3, 4, 5, 1, 3, 5, 3]
> find(3, a)
true
> find(6, a)
false
> position(3, a)
2
> position(6, a)
-1
> count(3, a)
3
> count(6, a)
0

このように、線形探索は簡単にプログラムできますが、大きな欠点があります。データ数が多くなると処理に時間がかかるのです。近年、パソコンの性能は著しく向上しているので、線形探索でどうにかなる場合もありますが、データ数が多くて時間かかかるのであれば、次の例題で取り上げる「二分探索」や他の高速な探索アルゴリズム ^[*1] を使ってみてください。

●二分探索

次は「二分探索 (バイナリサーチ：binary searching) 」を例題として取り上げます。線形探索の実行時間は要素数 N に比例するので、数が多くなると時間がかかるようになります。これに対し、二分探索は log₂ N に比例する時間でデータを探すことができます。

ただし、探索するデータはあらかじめ昇順に並べておく必要があります。この操作を「ソート (sort) 」といいます。二分探索は最初にデータをソートしておかないといけないので、線形探索に比べて準備に時間がかかります。

二分探索の動作を下図に示します。

              図 : 二分探索

二分探索は探索する区間を半分に分割しながら調べていきます。キーが 66 の場合を考えてみましょう。まず区間の中央値 55 とキーを比較します。データが昇順にソートされている場合、66 は中央値 55 より大きいので区間の前半を調べる必要はありません。したがって、後半部分だけを探索すればいいのです。

あとは、これと同じことを後半部分に対して行います。最後には区間の要素が一つしかなくなり、それとキーが一致すれば探索は成功、そうでなければ探索は失敗です。ようするに、探索するデータ数が 1 / 2 ずつ減少していくわけです。上図の場合、線形探索ではデータの比較が 6 回必要になりますが、二分探索であれば 4 回で済みます。また、データ数が 100 万個になったとしても、二分探索を使えば高々 20 回程度の比較で探索を完了することができます。

それでは、配列からデータを二分探索するプログラムを作ってみましょう。二分探索は繰り返しを使って簡単にプログラムできます。次のリストを見てください。

リスト : 二分探索

function binary_search(n, ary) {
    var low = 0;
    var high = ary.length - 1;
    while (low <= high) {
        var mid = Math.floor((low + high) / 2);
        if (n == ary[mid]) {
            return true;
        } else if (n < ary[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return false;
}

最初に、探索する区間を示す変数 low と high を初期化します。配列の長さは ary.length で取得し、最後の要素の位置を high にセットします。次の while ループで、探索区間を半分ずつに狭めていきます。まず、区間の中央値を求めて mid にセットします。JavaScript の数値は浮動小数点数なので、数学関数 floor() を使って整数値に変換しています。数学関数については JavaScript のリファレンスをお読みください。if 文で mid の位置にある要素と x を比較し、等しい場合は探索成功です。return で true を返します。

x が大きい場合は区間の後半を調べます。変数 low に mid + 1 をセットします。逆に、x が小さい場合は前半を調べるため、変数 high に mid - 1 をセットします。これを区間が二分割できるあいだ繰り返します。low が high より大きくなったら分割できないので繰り返しを終了し false を返します。

簡単な実行例を示しましょう。

> a = [11, 22, 33, 44, 55, 66, 77, 88, 99]
[11, 22, 33, 44, 55, 66, 77, 88, 99]
> binary_search(44, a)
true
> binary_search(40, a)
false

二分探索はデータを高速に探索することができますが、あらかじめデータをソートしておく必要があります。このため、途中でデータを追加するには、データを挿入する位置を求め、それ以降のデータを後ろへ移動する処理が必要になります。つまり、データの登録には時間がかかるのです。

したがって、二分探索はプログラムの実行中にデータを登録し、同時に探索も行うという使い方には向いていません。途中でデータを追加して探索も行う場合は、他の高速な探索アルゴリズムを検討してみてください。

●素数を求める (2)

それでは関数を使って、前回作成した素数を求めるプログラムを書き直して見ましょう。次のリストを見てください。

リスト : 素数を求める

// 素数か？
function primep(x, prime_list) {
    for (var i = 0; i < prime_list.length; i++) {
        var y = prime_list[i];
        if (y * y > x) break;
        if (x % y == 0) return false;
    }
    return true;
}

// 素数を求める
function prime(n) {
    var prime_list = [2];
    for (var x = 3; x < n; x += 2) {
        if (primep(x, prime_list)) prime_list.push(x);
    }
    return prime_list;
}

> prime(100)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

数値 x が素数か判定する処理を関数 primep() で行うように変更します。primep() は数値 x と素数を格納した配列 prime_list を受け取り、x が素数で割り切れれば false を返し、そうでなければ true を返します。

primep() を使うと、素数を求める関数 prime() は簡単にプログラムすることができます。primep() が true を返したら x を prime_list に追加するだけです。素数の判定処理を関数 primep() で行うことにより、関数 prime() はとてもわかりやすいプログラムになりました。

再帰定義

関数定義の中で、その関数自身を呼び出すことを「再帰呼び出し (recursive call) 」とか「再帰定義 (recursive definition) 」といいます。関数の定義に自分自身を使うことができるなんて、何か特別な仕掛があるのではないかと思われるかもしれません。ところが、再帰定義は特別なことではないのです。大昔のプログラミング言語ならばいざしらず、今では再帰呼び出しができないプログラミング言語のほうが珍しいでしょう。もちろん JavaScript の関数も再帰呼び出しが可能です。

●再帰定義の基本

再帰定義というと、Lisp / Scheme のような「関数型言語」の専売特許だと思われている方もいるでしょう。実際、Ｃ言語などの手続き型言語では、再帰定義を難しいテクニックの一つと思い込んでしまい、初心者の方は避けて通ることが多いように思います。再帰定義は今まで説明した関数の呼び出しとまったく同じなので、難しく考える必要はありません。慣れるまでちょっと苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができます。

まずは簡単な例を見てみましょう。階乗を計算するプログラムです。階乗の定義を下図に示します。

階乗の定義からわかるように、n の階乗は n - 1 の階乗がわかれば求めることができます。実は、これをそのままプログラムすることができます。次のリストを見てください。

リスト : 階乗

function fact(n) {
    if (n == 0) return 1;
    return n * fact(n - 1);
}

関数 fact() は引数 n が 0 であれば 1 を返し、そうでなければ n * fact(n - 1) の計算結果を返します。fact() の定義で fact() 自身を呼び出しています。これが再帰呼び出しです。

階乗と同じように再帰定義で表されるアルゴリズムはたくさんあります。階乗の計算は簡単なので、再帰呼び出しを使わなくても繰り返しでプログラムできますが、再帰で定義されるアルゴリズムのなかには、繰り返しに変換すると複雑なプログラムになってしまうものがあります。

このような場合は、素直に再帰定義を使ったほうがわかりやすいプログラムになり、間違いを犯す危険性が少なくなります。難しいアルゴリズムでも、再帰定義を使うと簡単にプログラムできる場合もあるのです。

実行結果は次のようになります。

> function fact(n) { if (n == 0) return 1; return n * fact(n - 1); }
undefined
> for (n = 0; n <= 10; n++) console.log(fact(n))
(2) 1
    2
    6
    24
    120
    720
    5040
    40320
    362880
    3628800
undefined

●再帰定義のポイント

それでは、再帰定義のポイントを説明しましょう。下図を見てください。

            図 : fact の再帰呼び出し（n:引数の値, value:返り値）

図は関数 fact(4) の呼び出しを表したものです。最初の呼び出し (Call:1) では、引数 n の値は 4 なので n の値を 1 減らして fact() を再帰呼び出しします。2 回目の呼び出しでは、引数 n の値に 3 が代入されます。ここで、最初に呼び出したときと 2 回目に呼び出したときでは、引数 n の値が違うことに注意してください。

関数の引数はローカル変数として扱われます。前回説明したように、ローカル変数には有効範囲（スコープ）があります。引数の場合、その関数が実行されている間だけ有効です。ローカル変数は関数呼び出しが行われるたびに新しく生成されて、そこに値が代入されます。そして、関数の実行が終了すると、生成されたローカル変数は廃棄されます。つまり、1 回目の呼び出しと 2 回目の呼び出しでは、引数 n は名前が同じでも異なる変数になるのです。ここが再帰呼び出しを理解するポイントの一つです。

プログラムを見ると変数 n は一つしかありませんが、再帰呼び出しが行われるたびに新しい変数 n が作られていくと考えてください。fact(4) を実行しているときの n は 4 であり、fact(3) を呼び出すときには、この n の値を書き換えるのではなく、新しい変数 n を用意して、そこに 3 を代入するのです。

同様に再帰呼び出しが行われ、5 回目の呼び出し (Call:5) で引数 n が 0 になります。このとき、if の then 節が実行され 1 が返されます。ここで再帰呼び出しが止まります。これを再帰呼び出しの「停止条件」といいます。ここが第 2 のポイントです。

停止条件がなかったり、あってもその条件を満たさない場合、関数を際限なく呼び出すことになり、JavaScript であればプログラムの実行は途中で停止します。再帰呼び出しを使う場合は、この停止条件に十分注意してください。

fact(0) は 1 を返して fact(1) に戻ります。fact(1) を実行しているあいだ、引数 n の値は 1 です。したがって、fact(1) の返り値は 1 * 1 を計算して 1 となります。あとは同様に、再帰呼び出しした関数の返り値を使って値を計算し、最後に fact(4) の値 24 を求めることができます。

●末尾再帰と繰り返し

再帰定義のなかで、処理の最後で再帰呼び出しを行う場合を「末尾再帰」といいます。英語では tail recursion ですが、日本語では末尾再帰のほかに末端再帰とか終端再帰と呼ぶことがあります。

末尾再帰の「末尾」とは、関数の最後で行われる処理のことです。とくに末尾で関数を呼び出すことを「末尾呼び出し (tail call) 」といいます。関数を呼び出す場合、返ってきたあとに行う処理のため、必要な情報を保存しておかなければいけません。ところが、末尾呼び出しはそのあとに実行する処理がありません。呼び出したあと元に戻ってくる必要さえないのです。

このため、末尾呼び出しはわざわざ関数を呼び出す必要はなく、アセンブリ言語のような低水準のレベルではジャンプ命令に変換することができます。これを「末尾呼び出し最適化 (tail call optimization) 」とか「末尾最適化」といいます。とくに末尾再帰は末尾で自分自身を呼び出しているので、関数の中で繰り返しに変換することができます。

また、相互再帰やもっと複雑な再帰呼び出しの場合でも、末尾最適化を適用することで、繰り返しに変換できる場合もあります。このように、再帰プログラムを繰り返しに変換してから実行することを「末尾再帰最適化 (tail recursion optimization) 」といいます。厳密にいうと末尾最適化なのですが、一般的には末尾再帰最適化と呼ばれることが多いようです。

Lisp などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルもしくは実行するときに、末尾再帰最適化を行う処理系があります。なかには Scheme ^[*1] のように、言語仕様に末尾再帰最適化を行うことを明記しているプログラミング言語もあります。

たとえば、階乗を計算する関数 fact() を思い出してください。

リスト : 階乗 (再掲)

function fact(n) {
    if (n == 0) return 1;
    return n * fact(n - 1);
}

fact() は最後に n と fact() の返り値を乗算しているので、このプログラムは末尾再帰ではありません。これを末尾再帰に変換すると次のようになります。

リスト : 階乗（末尾再帰）

function facti(n, a) {
    if (n == 0) return a;
    return facti(n - 1, a * n);
}

最後の再帰呼び出しで、facti() の返り値をそのまま返しているので、このプログラムは末尾再帰になっています。これで階乗を計算できるなんて、ちょっと不思議に思われるかもしれません。そこが再帰呼び出しの面白いところです。このプログラムでは引数 a の使い方がポイントです。

たとえば facti(4, 1) を実行すると、このプログラムでは 4 * 3 * 2 * 1 を計算します。このとき、計算の途中経過を引数 a に記憶しているのです。facti() の呼び出しを下図に示します。

facti(4, 1)
|   facti(3, 4)
|   |   facti(2, 12)
|   |   |   facti(1, 24)
|   |   |   |   facti(0, 24)
|   |   |   |   => a の値 24 を返す
|   |   |   => 24
|   |   => 24
|   => 24
=> 24

図 : facti() の動作

引数 a には計算途中の値が格納されていることがわかります。このような変数を「累算変数」とか「累算器」といいます。

関数型言語の場合、while 文や for 文などの繰り返しがないプログラミング言語があります。また、論理型言語 Prolog にも単純な繰り返しはありません。これらのプログラミング言語では、繰り返しのかわりに末尾再帰を使ってプログラミングを行い、末尾再帰最適化によりプログラムを高速に実行することができます。

実行結果を示します。

> for (x = 0; x < 10; x++) console.log(facti(x, 1))
(2) 1
    2
    6
    24
    120
    720
    5040
    40320
    362880

ところで、末尾再帰を繰り返しに変換することは簡単です。実際に関数 facti() を繰り返しに変換すると次のようになります。

リスト : 階乗 (繰り返し)

function fact_loop(n){
    var a = 1;
    for (; n > 1; n--) a *= n;
    return a;
}

手続き型言語に慣れている方は、こちらのプログラムのほうがわかりやすいかもしれません。実行結果は次のようになります。

> for (x = 0; x < 10; x++) console.log(fact_loop(x))
(2) 1
    2
    6
    24
    120
    720
    5040
    40320
    362880

繰り返しは再帰定義に比べると実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも繰り返しでプログラムしようとする方もいるでしょう。ところが、再帰定義を使うと簡単にプログラムできるが、繰り返しではとても複雑なプログラムになってしまう場合もあります。したがって、とくに問題がなければ再帰定義を繰り返しに変換する必要はないと思います。複雑なプログラムは、しばらくたつと書いた本人でさえ理解できなくなることがよくあります。わかりやすいプログラムがいちばんです

●フィボナッチ関数

もう一つ簡単な数値計算の例を示しましょう。フィボナッチ関数は階乗と同様に再帰的に定義される関数です。

フィボナッチ関数も再帰呼び出しを使えば簡単にプログラムできます。

リスト : フィボナッチ関数

function fibo(n) {
    if (n == 0 || n == 1) return 1;
    return fibo(n - 1) + fibo(n - 2);
}

> for (x = 0; x < 10; x++) console.log(fibo(x))
(2) 1
    2
    3
    5
    8
    13
    21
    34
    55

関数 fibo() は階乗の計算を行う関数 fact() とは違い、自分自身を 2 回呼び出しています。これを「二重再帰」といいます。fibo() の呼び出しをトレースすると下図のようになります。

        図 : 関数 fibo() のトレース

同じ値を何回も求めているため、fibo() の効率はとても悪いのです。この場合、二重再帰を「末尾再帰」に変換すると高速化することができます。そこで累算変数を使って、二重再帰を末尾再帰へ変換してみましょう。プログラムは次のようになります。

リスト : フィボナッチ関数（末尾再帰）

function fiboi(n, a1, a2) {
    if(n < 1) return a1;
    return fiboi(n - 1, a1 + a2, a1);
}

> for (x= 0; x < 10; x++) print(fiboi(x, 1, 0))
(2) 1
    1
    2
    3
    5
    8
    13
    21
    34
    55

累算変数 a1 と a2 の使い方がポイントです。現在のフィボナッチ数を変数 a1 に、ひとつ前の値を変数 a2 に格納しておきます。あとは a1 と a2 を足し算して、新しいフィボナッチ数を計算すればいいわけです。関数 fiboi() の呼び出しを下図に示します。

fiboi(5)
|  fibo(4, 1, 0)
|  |  fiboi(3, 2, 1)
|  |  |  fiboi(2, 3, 2)
|  |  |  |  fiboi(1, 5, 3)
|  |  |  |  |  fiboi(0, 8, 5)
|  |  |  |  |  => a1 の値 8 を返す
|  |  |  |  => 8
|  |  |  => 8
|  |  => 8
|  => 8
=> 8

  図 : 関数 fiboi() の呼び出し

二重再帰では、同じ値を何回も求めていたため効率がとても悪かったのですが、このプログラムでは無駄な計算を行っていないので、値を高速に求めることができます。もちろん、末尾再帰になっているので、末尾再帰最適化を行う処理系では、プログラムをより高速に実行することができます。

ちなみに、関数 fiboi() を繰り返しに変換すると次のようになります。

リスト : フィボナッチ関数（繰り返し）

function fibo_loop(n){
    var a1 = 1, a2 = 0;
    for( ; n > 0; n--){
        var a = a1;
        a1 += a2;
        a2 = a;
    }
    return a1;
}

> for (x= 0; x < 10; x++) console.log(fibo_loop(x));
(2) 1
    1
    2
    3
    5
    8
    13
    21
    34
    55

●ハノイの搭

再帰といえば忘れてはいけないのが「ハノイの塔」でしょう。ハノイの塔は、棒に刺さっている大きさが異なる複数の円盤を、次の規則に従ってほかの棒に移動させるパズルです。

1. 一回に一枚の円盤しか移動できない。
2. 小さな円盤の上に大きな円盤を置くことはできない。
3. 最初すべての円盤は一本の棒に刺さっていて、各円盤はそれより大きな円盤の上に置かれている。

ハノイの塔は、再帰を使えば簡単に解ける問題です。たとえば、3 枚の円盤が左の棒に刺さっているとします。この場合、いちばん大きな円盤を中央の棒に移すには、その上の 2 枚の円盤を右の棒に移しておけばいいですね。いちばん大きな円盤を中央に移したら、右の棒に移した 2 枚の円盤を中央の棒に移すことを考えればよいわけです。したがって、n 枚の円盤を左から中央の棒に移すプログラムは次のように定義できます。

1. ｎ－１枚の円盤を左から右に移す
2. ｎ枚目の円盤を左から中央へ移す
3. ｎ－１枚の円盤を右から中央へ移す

これを素直にプログラムすると次のようになります。

リスト : ハノイの塔

function hanoi(n, from, to, via){
    if (n == 1) {
        console.log(from + " => " + to);
    } else {
        hanoi(n - 1, from, via, to);
        console.log(from + " => " + to);
        hanoi(n - 1, via, to, from);
    }
}

n は動かす円盤の枚数、from は移動元の棒、to は移動先の棒、via は残りの棒を示します。棒は文字列で表します。円盤の枚数が 1 枚の場合は簡単ですね。from にある円盤を to へ移すだけです。これが再帰の停止条件になります。この動作を print() で表示します。

円盤が複数枚ある場合、from にある円盤の n - 1 枚を via に移します。この処理は hanoi を再帰呼び出しすればいいですね。次に、残りの 1 枚を to に移します。これを print() で表示します。そして、via に移した n - 1 枚の円盤を to に移します。この処理も hanoi を再帰呼び出しするだけです。これでプログラムは完成です。それでは実行してみましょう。

> hanoi(3, "A", "B", "C")
A => B
A => C
B => C
A => B
C => A
C => B
A => B
undefined

このように、再帰定義を使うと「ハノイの塔」を簡単に解くことができます。