TypeScriptの型で遊ぶ時、再帰制限を（合法的に）突破する

:::note info
2024/9/11追記：現在のバージョン(5.6) において、再帰深度上限は1000になっています。多くのケースはこの記事のような手法を使うまでもなく単純な再帰で解決できるはずです
:::

TypeScriptの型の再帰は50が上限です。

先日、 @kgtkr さんが[TypeScriptの型で遊ぶ時、再帰制限を無効化する](https://qiita.com/kgtkr/items/eff20225e4bf9b159110)という記事で、 その再帰制限を、ソースコードを書き換えることで突破して、型レベル BrainF\*\*k などで遊んでいるのを見ました。

タイトルで合法的と言っておきながら、別にソースコードを書き換えるのが何らかの法に触れる訳ではないのですが、とは言え @kgtkr さんも記事の中で、

> * 当然ですがプロダクトで使うことは想定していません、やめましょう。

と言っている通り、これをプロダクトに採用するわけにはいきません。

というわけで、ソースコード書き換えをせずに再帰制限を突破してやろう、というのがこの記事の趣旨です。

## 文字列を分割する（再帰制限に引っかかる例）

[Template literal types](https://github.com/microsoft/TypeScript/pull/40336) がマージされたので、 typescript@next を使えば文字列リテラル型を分割できます。単純に考えると、こんなコードが思い浮かびますね。

```ts
type ToTuple<T extends string> = T extends `${infer U}${infer V}` ? [U, ...ToTuple<V>] : [];
type A = ToTuple<'Nyan'>; // ['N', 'y', 'a', 'n']
```

-> [Playground](https://www.typescriptlang.org/play?ts=4.1.0-dev.20200913#code/C4TwDgpgBAKg9jArmANhAPDKEAewIB2AJgM5QnABOAlgQOYB8UAvLNnoaVAAYAkA3rQBmESlACqAXwHDRUAGqTuUAPxQA2uIA0UAHT74SVBnkMAulABcGswG4AsAChQkKAEEWsBMjToA5AByIACGBH4MtlAA9FEagX46fiAJUH7BKX5hZk5AA)で見る

このまま文字列を長くしていくと、23文字までは大丈夫ですが、

```ts
type ToTuple<T extends string> = T extends `${infer U}${infer V}` ? [U, ...ToTuple<V>] : [];
type A = ToTuple<'Nyanyanyanyanyanyanya!!'>;
type B = A['length']; // 23
```
-> [Playground](https://www.typescriptlang.org/play?ts=4.1.0-dev.20200913#code/C4TwDgpgBAKg9jArmANhAPDKEAewIB2AJgM5QnABOAlgQOYB8UAvLNnoaVAAYAkA3rQBmESlACqAXwHDRUAGqTuUAPxQA2uIA0UAHT74SVBnkMAulABcGswG4AsAChQkKAEEWsBMjToA5AByIACGBCFhoeFRkcEAhLF+DA7O4NAAQp5u6n5o9MAAFn52UAD0JVAATADMTkA)で見る

次で死にます。つらい。

```ts
type ToTuple<T extends string> = T extends `${infer U}${infer V}` ? [U, ...ToTuple<V>] : [];
type A = ToTuple<'Nyanyanyanyanyanyanya!!!'>; // Type instantiation is excessively deep and possibly infinite.(2589)
type B = A['length'];
```

-> [Playground](https://www.typescriptlang.org/play?ts=4.1.0-dev.20200913#code/C4TwDgpgBAKg9jArmANhAPDKEAewIB2AJgM5QnABOAlgQOYB8UAvLNnoaVAAYAkA3rQBmESlACqAXwHDRUAGqTuUAPxQA2uIA0UAHT74SVBnkMAulABcGswG4AsAChQkKAEEWsBMjToA5AByIACGBCFhoeFRkcEAhPF+DLZQAPQpsODQtBShwNTBeXAEUNRkuADGECQk1ABuECggUEQQEGBQoURQYHDV1ABGjSUEQrTU+LoAFABMAKwAHACcAJROLtAAQp5u6n5o9MAAFn52TkA)で見る

再帰制限が50なのに23で頭打ちになっているということは1回の `ToTuple` の再帰の間に内部の再帰カウンタが2回インクリメントされているということになります。コードを追っていないので詳しく分かりませんが、 `...ToTuple<V>` で呼び出した結果を展開しているあたりが問題なのかもしれません。
これは比較的簡単に回避できて、少し書き方を変えるだけで、

```ts
type ToTuple<T extends string, Result extends string[] = []> = T extends `${infer U}${infer V}` ? ToTuple<V, [...Result, U]> : Result;
type A = ToTuple<'Nyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!'>;
type B = A['length']; // 45
```

-> [Playground](https://www.typescriptlang.org/play?ts=4.1.0-dev.20200913#code/C4TwDgpgBAKg9jArmANhAPDKEAewIB2AJgM5QnABOAlgQOYA0UAShCYisNnoaeVbToBtALpQAvFFEA+CbG75iZAAYASAN60AZhEpQAqgF8N23VABqh5VAD8sBMjTpzTIQDoPrdpyb6RsgC4WNg5gAG4AWAAoUEgoAEE5eCRUDAByADkQAEMCHLzc-KLCkoKy4vLsgEIatOlImPBoACE5eKE0tHpgAAs0kTCoAHohqAAWAFZooA)で見る

とまあこのくらいまで伸ばすことが可能です。
これで上限の50に近付きましたね。しかしこれ以上はこのやり方では無理で、46文字以上にするとエラーになります。

どうすればいいんだ……やはりソースコードをいじるしかないのか……。

と、なる前に、ちょっと考え方を変えてみましょう。

## 再帰の再帰

再帰制限というのは、つまりスタックの高さに対する制限です。
`ToTuple` が 46 文字分で引っかかったのは、

```
---------------
ToTuple<T45>  |
ToTuple<T44>  |
...          50個
ToTuple<T4>   |
ToTuple<T3>   |
ToTuple<T2>   |
ToTuple<T1>   |
...           |
---------------
```

とまあこんな感じで50個分のスタックがいっぱいになったからです。1文字読む度に1個スタックが高くなるのですから、このままの実装では上限を突破できません。
しかし、再帰制限というのはあくまでスタックの高さに対する制限です。ステップ数の制限ではありません。
天井が低いのでこれ以上皿が積めないなら、横にもう一個山を作ってしまえば良いのです。

```
----------------------------------
ToTuple<T45>  |   ToTuple<T90>   |  
ToTuple<T44>  |   ToTuple<T89>   |  
...          50個 ...          50個
ToTuple<T4>   |   ToTuple<T49>   |  
ToTuple<T3>   |   ToTuple<T48>   |  
ToTuple<T2>   |   ToTuple<T47>   |  
ToTuple<T1>   |   ToTuple<T46>   |
...           |   ...            |
----------------------------------
```

横のもう一個の山をどうやって増やすかというと、TypeScriptの型レベル計算にはループ構文はないので、やはり再帰でやらなければなりません。なので上図のように真横に山を増やすことはできない（再帰する時にどうしてもスタックを消費するため）のですが、例えば、
「最大20文字読み取る」という操作Aと、「Aを20回繰り返す」という操作Bを考えてみると、20*20で400文字読み取れることになります。それでいて、スタックの高さは、20回再帰したときのBの高さ+20回再帰したときのAの高さが一番高くなるはずなので、それでも40回で、上限に達しない**はず**です(フラグ)。

なのでとりあえず、 `ToTuple` を上限20文字まで読んでTupleにするように改造してみましょう。この後同じようなジェネリクスを何個か作ることになるので、このジェネリクスは `ToTuple0` とします。

```ts
type First<T extends string> = T extends `${infer U}${infer _}` ? U : never;
type RemoveFirst<T extends string> = T extends `${infer _}${infer U}` ? U : never;

type ToTuple0<T extends string, Result extends string[] = [], Counter extends unknown[] = []> =
    ['', Counter['length']] extends { 0: T } | { 1: 20 } ? [T, Result] :
    ToTuple0<RemoveFirst<T>, [...Result, First<T>], [...Counter, unknown]>;

type A = ToTuple0<'Nyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!'>;
type B = A[1]['length']; // 20
```

-> [Playground](https://www.typescriptlang.org/play?ts=4.1.0-dev.20200913#code/C4TwDgpgBAYglgJwM7ADwBUoQB7AgOwBMkoUE58BzAPigF4pMc8iSADAEgG8KAzCBFACqAX258BUAPoi2UAPzCoALij4IANwEBuALAAoUJCgAlCAFsA9lvjI0TXAWKlg5KrQYOWzzj3z9BGXF-SVE5RSEVNU0dAwMjaHRLdABXMAAbCAAGDCxHVhc3SgAaUwgkFPTgPO8SMgpKAG0AXXooFtKAYUsU-DxBZicSXoBrfEsAd3wWtpaPAyhF9oByZa6evoFG5cyqYAALZebWwYKuKCzVTBEoAB8oc4BGVQAmLKgbxUb0UrMKqtaygWSySqQy2VQZisNkQKAw1FKjQAdCi-pVgKVbHD0NRmoiUUjur1+qVRuMps1qHp9PFwNAAIJtUFpTI5ZYAORAAEN8NzeTy+YKBcL+aKhWKuQBCaXLKm04wAITa9Maj2a212lAOR20UAA9HqoG8DEA)で見る

一気に複雑になって、謎の判定式が含まれるようになりました。 `['', Counter['length']] extends { 0: T } | { 1: 20 } } ?` というのが何かと言うと、 `'' extends T` もしくは `Counter['length'] extends 20` のどちらかを満たしているということを表す条件式です。
どうやらTypeScriptでは再帰の途中でConditional Typesが含まれると、そこで再帰カウンタが増えてしまうようなのですが、 `T1 extends U1` と `T2 extends U2` のどちらかを満たすという条件を `[T1, T2] extends { 0: U1 } | { 1: U2 }` という条件に置き換えることで、再帰カウンタの上昇を1回に抑えることができます。
ここでは利用しませんが、 同様に、`T1 extends U1` と `T2 extends U2` の両方を満たすという条件は、 `[T1, T2] extends [U1, U2]` と表記することも可能です。

つまり、`T` が空文字か、 `Counter` の長さが 20 だった時に `[T, Result]` を返す、そうでなければ `ToTuple0` を再帰的に呼び出す、という処理を行っている訳ですね。
こうすることによって、どんなに長い文字列リテラル型を渡しても再帰制限に引っかからない代わりに、20文字までしか分割しないジェネリクスが作れました。次は、このジェネリクスを再帰的に呼び出すジェネリクスをつくります。

```ts
type ToTuple1<T extends string, Result extends string[] = [], Counter extends unknown[] = []> =
    ToTuple0<T, Result> extends [infer T, infer Result] ?
    ['', Counter['length']]  extends { 0: T } | { 1: 19 } ? Result :
    ToTuple1<Extract<T, string>, Extract<Result, string[]>, [...Counter, unknown]> :
    never;

type A = ToTuple1<'Nyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!!'>;
type B = A['length']; // 100
```

-> [Playground](https://www.typescriptlang.org/play?ts=4.1.0-dev.20200913#code/C4TwDgpgBAYglgJwM7ADwBUoQB7AgOwBMkoUE58BzAPigF4pMc8iSADAEgG8KAzCBFACqAX258BUAPoi2UAPzCoALij4IANwEBuALAAoUJCgAlCAFsA9lvjI0TXAWKlg5KrQYOWzzj3z9BGXF-SVE5RSEVNU0dAwMjaHRLdABXMAAbCAAGDCxHVhc3SgAaUwgkFPTgPO8SMgpKAG0AXXooFtKAYUsU-DxBZicSXoBrfEsAd3wWtpaPAyhF9oByZa6evoFG5cyqYAALZebWwYKuKCzVTBEoAB8oc4BGVQAmLKgbxUb0UrMKqtaygWSySqQy2VQZisNkQKAw1FKjQAdCi-pVgKVbHD0NRmoiUUjur1+qVRuMps1qHp9PFwIlkmlMo9cqdnPUqL9yuiakNCg0ZgwOlAiZsBvlnGTJtNWoLKfRgYtQYyIT8yv9gLRWSRGhJBKrdWr0a15AqVmthRt+ttdpQDkdWjyzhcrh87g8oM8PQBOV2KNFVFSmpXg5kAUVwCAAhgBjeyldk0Urh1wxtD+jF8qhzfEokUkqCSim0IH6JbRLQIam04wAQTawaZqGWADkQJH8G2O+3Oz3u32uwPe4P+0PRyPx8PJ2OuwBCOcz5ZU6vQABCbRr1oItsOzW0UAA9PuPVksgYgA)で見る

100文字だって読み込める。
やっていることは何かというと、まず `ToTuple0` を呼び出して、その結果を型推論を利用して受け取ります。
その後は同じような条件分岐を行って、 `Counter` が上限に達していなかったら再帰する処理になっています。
先程と違って上限が19になっているのは、判定の前に `ToTuple0` の呼び出しが一回挟まるからで、上限に達したと判定された時には `ToTuple0` は20回呼び出されたことになります。

これで理論的には400文字まで読めるはずです。やってみましょう。

```ts
type A = ToTuple1<`
Nyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!
Nyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!
Nyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!
Nyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!
`>; // Type instantiation is excessively deep and possibly infinite.(2589)
type B = A['length'];
```

-> [Playground](https://www.typescriptlang.org/play?ts=4.1.0-dev.20200913#code/C4TwDgpgBAYglgJwM7ADwBUoQB7AgOwBMkoUE58BzAPigF4pMc8iSADAEgG8KAzCBFACqAX258BUAPoi2UAPzCoALij4IANwEBuALAAoUJCgAlCAFsA9lvjI0TXAWKlg5KrQYOWzzj3z9BGXF-SVE5RSEVNU0dAwMjaHRLdABXMAAbCAAGDCxHVhc3SgAaUwgkFPTgPO8SMgpKAG0AXXooFtKAYUsU-DxBZicSXoBrfEsAd3wWtpaPAyhF9oByZa6evoFG5cyqYAALZebWwYKuKCzVTBEoAB8oc4BGVQAmLKgbxUb0UrMKqtaygWSySqQy2VQZisNkQKAw1FKjQAdCi-pVgKVbHD0NRmoiUUjur1+qVRuMps1qHp9PFwIlkmlMo9cqdnPUqL9yuiakNCg0ZgwOlAiZsBvlnGTJtNWoLKfRgYtQYyIT8yv9gLRWSRGhJBKrdWr0a15AqVmthRt+ttdpQDkdWjyzhcrh87g8oM8PQBOV2KNFVFSmpXg5kAUVwCAAhgBjeyldk0Urh1wxtD+jF8qhzfEokUkqCSim0IH6JbRLQIam04wAQTawaZqDYBgAciBI-h252O13ez3+93B32hwPh2PRxOR1Px92AITz1szpeT5fTlfrteb5fz2eLjerg-7o9b4-jnd7k+Xw9X0+3tfn-RsKlQAD0L8YdKgFBQHeAcEjf6WPgX4kDg0blEgcBaOkIBQIQEAQGAUAdoQUBgJYSCQQARjBX7+BQcB4EiAAULwAKwABxegAlNW0AAEJtDW1oELahzNNSQA)で見る

**駄目でした**(フラグ回収)

敗因は、Conditional Types を2重に使わないといけないため、再帰カウンタが2回インクリメントされてしまうことです。つまり、 `ToTuple0` の再帰一回のコストが1なのに対して、 `ToTuple1` の再帰1回のコストは2とカウントする必要があるようです。色々試してみましたが、コストの合計が 46 以下になればエラーが出ないので、その範囲で最も読める文字数が大きい組み合わせは、 `ToTuple0` を22回再帰して `ToTuple1` を12回再帰するか、 `ToTuple0` を24回再帰して `ToTuple1` を11回再帰するのどちらかでした。つまり最大264文字まで読み取れることになります。

```ts
type First<T extends string> = T extends `${infer U}${infer _}` ? U : never;
type RemoveFirst<T extends string> = T extends `${infer _}${infer U}` ? U : never;

type ToTuple0<T extends string, Result extends string[] = [], Counter extends unknown[] = []> =
    ['', Counter['length']] extends { 0: T } | { 1: 22 } ? [T, Result] :
    ToTuple0<RemoveFirst<T>, [...Result, First<T>], [...Counter, unknown]>;

type ToTuple1<T extends string, Result extends string[] = [], Counter extends unknown[] = []> =
    ToTuple0<T, Result> extends [infer T, infer Result] ?
    ['', Counter['length']]  extends { 0: T } | { 1: 11 } ? Result :
    ToTuple1<Extract<T, string>, Extract<Result, string[]>, [...Counter, unknown]> :
    never;

type A = ToTuple1<`
Nyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!
Nyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!
Nyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!
Nyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!
`>;
type B = A['length']; // 264
```

-> [Playground](https://www.typescriptlang.org/play?ts=4.1.0-dev.20200913#code/C4TwDgpgBAYglgJwM7ADwBUoQB7AgOwBMkoUE58BzAPigF4pMc8iSADAEgG8KAzCBFACqAX258BUAPoi2UAPzCoALij4IANwEBuALAAoUJCgAlCAFsA9lvjI0TXAWKlg5KrQYOWzzj3z9BGXF-SVE5RSEVNU0dAwMjaHRLdABXMAAbCAAGDCxHVhc3SgAaUwgkFPTgPO8SMgpKAG0AXXooFtKAYUsU-DxBZicSXoBrfEsAd3wWtpaPAyhF9oByZa6evoFG5cyqYAALZebWwYKuKCzVTBEoAB8oc4BGVQAmF6gbxUb0UrMKqtaygWSySqQy2VQZisNkQKAw1FKjQAdCi-pVgKVbHD0NRmoiUUjur1+qVRuMps1qHp9PFwIlkmlMo9cqdnPUqL9yuiakNCg0ZgwOlAiZsBvlnGTJtNWoLKfRgYtQYyIT8yv9gLRWSRGhJBKrdWr0a15AqVmthRt+ttdpQDkdWjyzhcrh87g8oM8PY9XYo0VUVKaleDmQBRXAIACGAGN7KV2TRSmHXNG0H6MXyqHN8SiRSSoJKKbQgfoltEtAhqbTjABBNpBpmoNgGAByIAj+DbHfbnZ73b7XYHvcH-aHo5H4+Hk7HXYAhHOW9PFxOl1Pl2vVxul3OZwv1yv93vD5uj2Pt7vjxeD5eTzfV2f9GwqVXoAAhNrV60EW2HZraKAAen-KAXgANgAFgMIA)で見る

## 再帰の再帰の再帰

さて。

これでFinish！？な訳無いデショ！

264文字、当初の45文字に比べれば6倍近く読めるようになりましたが、ここで終わっては所詮その程度。英数字なら1ツイートに収まってしまいます。せめて1000文字くらいは行きたい。
どうするか。同じことをします。
つまり、 `ToTuple0` を繰り返し呼ぶ `ToTuple1` を作ったように、 `ToTuple1` を繰り返し呼ぶ `ToTuple2` を作るのです。

作りました。なお `ToTuple1` も `Result` ではなく `ToTuple0` と同じように `[T, Result]` を返す仕様に改造してあります。

```ts
type ToTuple2<T extends string, Result extends string[] = [], Counter extends unknown[] = []> =
    ToTuple1<T, Result> extends [infer T, infer Result] ?
    ['', Counter['length']]  extends { 0: T } | { 1: 7 } ? Result :
    ToTuple2<Extract<T, string>, Extract<Result, string[]>, [...Counter, unknown]> :
    never;
```

-> [Playground](https://www.typescriptlang.org/play?ts=4.1.0-dev.20200913#code/C4TwDgpgBAYglgJwM7ADwBUoQB7AgOwBMkoUE58BzAPigF4pMc8iSADAEgG8KAzCBFACqAX258BUAPoi2UAPzCoALij4IANwEBuALAAoUJCgAlCAFsA9lvjI0TXAWKlg5KrQYOWzzj3z9BGXF-SVE5RSEVNU0dAwMjaHRLdABXMAAbCAAGDCxHVhc3SgAaUwgkFPTgPO8SMgpKAG0AXXooFtKAYUsU-DxBZicSXoBrfEsAd3wWtpaPAyhF9oByZa6evoFG5cyqYAALZebWwYKuKCzVTBEoAB8oc4BGVUeAVigbxUb0UrMKqtaygWSySqQy2VQZisNkQKAw1FKjQAdCi-pVgKVbHD0NRmoiUUjur1+qVRuMps1qHp9PFwIlkmlMo9cqdnPUqL9yuiakNCg0ZgwOlAiZsBvlnGTJtNWoLKfRgYtQYyIT8yv9gLRWSRGhJBKrdWr0a15AqVmthRt+ttdpQDkdWjyzhcrh87g8oM8oAB2V1fVVogEqU1K8HMgCiuAQAEMAMb2UrsmilCOuWNoAMYvlUOb4lEiklQSUU2hA-RLaJaBDU2nGEOZABMLPFdVcDU56sdbNb2Zl7TxFuJki1hfwYylAr78zLIIZoYw7fRmub7QN+pCggzxtN23N+a2OwItsOx0Ww-Ol0YrvuT1UPs+hqqQenitnDdQKejcfnWaTUA-achLkqgTbsmkpXNCUtARSVHcl8DlUty3UStq0MOkoAAQTaOsIEbNgDAAORAKN8GI0iSLIyiKOo8jaKouiaPopjGJYhi2OY8iAEJuMIji+NY-j2IE4ShNE-juM43iRMEmTpLksT5OYiSpIU1TZLUxTNKE5T9CIrT1IM-SjO0njdMMjSLPMqzhJ0vTLOM6z7Ps2zHNchz3JMySzI8tynN8qiXJ8oK-KCwKQvC-zQtMtgqRraAACE2gw61DztZptCgAB6TKoAATgANiyAwgA)で見る

コスト上限は47で、 `ToTuple0` を15回、 `ToTuple1` を8回、 `ToTuple2` を8回繰り返すパターンが最も効率が良く、960文字まで読み取れます。憧れの1000文字まであと少し。

## 再帰の再帰の再帰の再帰の……

同じようにして `ToTuple3`, `ToTuple4`, と追加していきます。それぞれの最適な繰り返し回数の組み合わせは以下のようになります

||繰り返し回数|読み取り可能文字数|
|:--|:--|:--|
|`ToTuple0`|45|45|
|`ToTuple0`, `ToTuple1`|22, 12|264|
|`ToTuple0`, `ToTuple1`, `ToTuple2`|15, 8, 8|960|
|`ToTuple0`, `ToTuple1`, `ToTuple2`, `ToTuple3`|12, 6, 6, 6|2592|
|`ToTuple0`, `ToTuple1`, `ToTuple2`, `ToTuple3`, `ToTuple4`|9, 5, 5, 5, 5|5625|
|`ToTuple0`, `ToTuple1`, `ToTuple2`, `ToTuple3`, `ToTuple4`, `ToTuple5`|10, 4, 4, 4, 4, 4|10240|
|`ToTuple0`, `ToTuple1`, `ToTuple2`, `ToTuple3`, `ToTuple4`, `ToTuple5`, `ToTuple6`|3, 4, 4, 4, 4, 4, 4|12288|
|`ToTuple0`, `ToTuple1`, `ToTuple2`, `ToTuple3`, `ToTuple4`, `ToTuple5`, `ToTuple6`, `ToTuple7`|10, 3, 3, 3, 3, 3, 3, 3|21870|
|`ToTuple0`, `ToTuple1`, `ToTuple2`, `ToTuple3`, `ToTuple4`, `ToTuple5`, `ToTuple6`, `ToTuple7`, `ToTuple8`|4, 3, 3, 3, 3, 3, 3, 3, 3|26244|

DB設計でこんなの書いたら怒られそうな表になってしまった。なお5625から先は理論値です。試してみたらブラウザのV8エンジンが落ちました。4701までは大丈夫だったのでローカルで頑張れば行けるかもしれない。
再帰制限は回避できても、効率的にはかなり良くない計算をやっているので（内部的には再帰1回ごとにサイズを+1した配列が作られる）メモリもCPUもバカ食いしますが、1000文字くらいならなんとかなりそうです。1000文字あればけっこう型遊びができますね、そう、こんな風に。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/71477/af5bffc3-1863-5744-adc5-9fd6b63bc447.png)