🐝

【TS】政党名で学ばない再帰関数

2020/11/01に公開

TypeScript

tech

はじめに

いきなりですが、以下の記事をご覧になられたことはあるでしょうか？

参考：Qiita | 【数学】NHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党

タイトルからも分かる通り、某政党名を数学的見地から解説した内容で非常に読み応えがあります。
※数列や漸化式のような高校数学の知識があれば(なくても)楽しく読める内容になっていますのでオススメです。

その中でPerlで記載された下記のようなコードがあります。

# 引用：https://qiita.com/MirrgieRiana/items/da7dade622770a04d8f7
sub N {
  my $n = shift;
  return $n == 0 ? "国民"
       : $n == 1 ? "NHK"
       :           N($n - 1)."から".N($n - 2)."を守る党";
}
print N(4), "\n";

ざっくり説明すると「NHKから国民を守る党」という文字列を起点に漸化式で表現する場合に、
N(0)=国民およびN(1)=NHKとすることで

N(2)=N(1)からN(0)を守る党
N(3)=N(2)からN(1)を守る党
N(n)=N(n−1)からN(n−2)を守る党

という結果を導き出しており、それをコードで表現すると上記のような内容になるというものです。

これを見た時「これは再帰関数の題材として良いのでは？」と思いました。
以前会社の新人に再帰関数の説明をした時は「任意の深さのディレクトリを再起的に探索していくプログラム」を書いて説明していたのですが、如何せん面白味に欠ける内容だったのでウケがイマイチでした。

その点この題材は出力内容の絵面的にも面白いため、再帰関数という内容に焦点を当ててまとめてみたいと思います。
ついでにPerlにはあまり詳しくないので、自信のあるTypescriptで記載してみることにします。

そもそも再帰関数って？

再帰のWikipediaには以下のような内容で説明されています。

再帰（さいき）は、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。

従って再帰関数とは「関数の中で関数自身を呼び出す関数」ということになります。
「それって無限ループにならないの？」と思われた方は鋭いです。
明確に定義されているわけではないかと思いますが、私の中では無限ループに陥らないために再帰関数は以下の条件を満たしている必要があると思います。

再帰処理の終了フローが用意されている

10から始まって0までカウントダウンしながらコンソールに表示していくプログラムを再帰関数を使って記載する例を考えます。

const rec = (i: number): void => {
  // iが0未満になったら終了
  if(i < 0) return;
  // iをコンソールに表示
  console.log(i);
  // iをデクリメントして再帰呼び出し
  rec(i-1);
}

出力結果は以下になります。

コード中のif(i < 0) return;が終了フローになります。
もしこの分岐がなかったらiは-1,-2,-3と無限にデクリメントし続けてしまいます。
※数値的にはビット数の限界があるため厳密には「無限にデクリメント」はしないですがrec()は無限に呼び出されるため終了することがないです。

よって、再帰関数を考える場合は必ず「その再帰関数を終了させる処理」を用意する必要があります。
大概の再帰処理には数値が絡んでくると思うので「カウンタとして扱う数値が一定の条件に達したら終了」とすることが多いかと思います。
冒頭で述べた「ディレクトリの再帰探索」の場合は「入れ子となっているディレクトリがnullになった時」が終了条件にあたると思います。

某政党名の再帰関数をTypescriptで再現

前置きが長くなりましたが本題です。
元の記事に倣って

N(0)=国民
N(1)=NHK
N(2)=N(1)からN(0)を守る党
N(n)=N(n−1)からN(n−2)を守る党

となるような関数を定義します。

const nhk = (n: number): string => {
  // 終了条件①
  if(n===0) return '国民';
  // 終了条件②
  else if(n===1) return 'NHK';
  // 再帰呼び出し
  else return `${nhk(n-1)}から${nhk(n-2)}を守る党`;
}

console.log(nhk(0));
// -> 国民
console.log(nhk(1));
// -> NHK
console.log(nhk(2));
// -> NHKから国民を守る党
console.log(nhk(3));
// -> NHKから国民を守る党からNHKを守る党

数値型なら何でも渡せてしまうので厳密にはn < 0の場合も考慮する必要がありますが、元コードをTypescriptで再現した場合は上記のようになります。

終了条件が2つあるのは、再帰呼び出しする段階でnを2減算するためです。
これでTypescriptで某政党名を再起的に処理する関数を作成することができました。

おまけ「何を守っているかを分かりやすくする」

再帰関数を学習する教材としては十分ですが、先のnhkを引数10で実行した場合は下記のような結果になります。

console.log(nhk(10));

出力

NHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党からNHKから国民を守る党からNHKを守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党からNHKから国民を守る党からNHKを守る党を守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党からNHKから国民を守る党からNHKを守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党を守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党からNHKから国民を守る党からNHKを守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党からNHKから国民を守る党からNHKを守る党を守る党を守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党からNHKから国民を守る党からNHKを守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党からNHKから国民を守る党からNHKを守る党を守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党からNHKから国民を守る党からNHKを守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党を守る党を守る党を守る党

これでは何が何を守っているのかがよく分かりません。
人は守るべきものがあって初めて強くなれるので、何を守るのかは明確であるべきです。

複雑な構造になっているように見えますが「AからBを守る党」という日本語としてはシンプルな構造のはずです。
そこで先ほどの関数に少しだけ手を入れます。

修正後

const nhk = (n: number, isChild?: boolean):string => {
    return  n===0? '国民'
            :n===1? 'NHK'
            :`${
                (isChild?'':'「') +
                nhk(n-1,true) +
                (isChild?'':'」\n')
            }から${
                (isChild?'':'\n「') +
                nhk(n-2,true) + 
                (isChild?'':'」\n')
            }を守る党`
}

if...elseを三項演算子に置き換えて簡略化していますが、ポイントは第二引数のisChildが追加された点です。
これは初回の呼び出しではundefiend、再帰呼び出し時にtrueの値とすることで、実行段階で関数自身が「今は再帰呼び出しされている最中なのかどうか」を理解することができるようになります。
こうすることで、トップレベルの処理時には「守るべき対象」と「何から守るべきか」に括弧を付けることができるようになります。

console.log(nhk(10));

修正後出力

「NHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党からNHKから国民を守る党からNHKを守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党からNHKから国民を守る党からNHKを守る党を守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党からNHKから国民を守る党からNHKを守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党を守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党からNHKから国民を守る党からNHKを守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党からNHKから国民を守る党からNHKを守る党を守る党を守る党を守る党」
から
「NHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党からNHKから国民を守る党からNHKを守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党からNHKから国民を守る党からNHKを守る党を守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党からNHKから国民を守る党からNHKを守る党を守る党からNHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党を守る党を守る党」
を守る党

なるほど。
これで守るべきものが何か分かりましたね(私にはよく分かりませんでしたが)。