Fibonacci 数列

题目

实现一个泛型 Fibonacci<T>，接受一个数字 T，返回对应位置的 Fibonacci 数。

数列从以下开始：
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

例如：

type Result1 = Fibonacci<3> // 2
type Result2 = Fibonacci<8> // 21

解题思路

核心思路：TypeScript 没有内置的算术运算，但元组的长度就是数字字面量类型。我们可以用 1 的元组来表示数字，通过展开运算符 + ["length"] 来实现加法。

计算 Fibonacci 数需要同时追踪三个状态：当前在数列中的位置、前一个值、当前值。通过递归让这三个值一起向前推进，用"长度即计数器"的元组来判断何时停止。

type Fibonacci<
  T extends number,
  // 当前位置计数器（从 1 开始）
  Index extends 1[] = [1],
  // 前一个 Fibonacci 值（以元组表示）
  Prev extends 1[] = [],
  // 当前 Fibonacci 值（以元组表示）
  Curr extends 1[] = [1]
> = Index["length"] extends T
  ? Curr["length"]
  : Fibonacci<T, [...Index, 1], Curr, [...Prev, ...Curr]>

以 Fibonacci<5> 为例逐步演示：

步骤	`Index` 长度	`Prev` 长度	`Curr` 长度
1	1	0	1
2	2	1	1
3	3	1	2
4	4	2	3
5	5	3	5 ✓

当 Index["length"] === T 时，返回 Curr["length"]。

每步的转换逻辑：

Index 增长 1（表示移动到下一个位置）
新的 Prev = 旧的 Curr
新的 Curr = 旧的 Prev + Curr（展开两个元组合并）

深度解析

为什么用元组而非数字

TypeScript 的条件类型可以检查类型之间的相等性，但无法直接对数字字面量类型进行算术运算——3 + 2 在类型位置是非法的。然而，[...Array<1>, ...Array<1>]["length"] 完全合法——它展开两个元组并将结果长度读取为数字字面量。

这是类型层面数学运算的基础技巧，在 type-challenges 中无处不在：数字变成元组，加法变成元组拼接，"这个数等于 N 吗？"变成 Tuple["length"] extends N。

三状态累加器模式

经典的 Fibonacci 函数接受 (prev, curr) 并按 (curr, prev + curr) 向前推进。这里完全复刻了同样的逻辑，只是携带了三个状态：Index（位置计数器）、Prev 和 Curr。这种"将累加器作为类型参数携带"的模式，是将迭代算法转化为尾递归类型函数的标准方式。

TypeScript 会递归地求解这些类型——每次"迭代"就是一次递归类型实例化。默认递归深度约为 1000 次，足以计算合理范围内的 Fibonacci 数。

为什么 Index 的初始值从 `[1]` 开始

这道题是 1 索引的：Fibonacci<1> = 1，Fibonacci<2> = 1，Fibonacci<3> = 2，以此类推。将 Index 初始化为 [1]（长度为 1），Curr 初始化为 [1]（值为 1），当 T = 1 时基准条件 Index["length"] extends T 直接返回 1，无需任何特殊处理。

将 Prev 初始化为 []（空元组，长度为 0），意味着第一步得到 Curr = [...[], ...[1]] = [1]——这正是正确答案，因为 fib(2) = 1。

元组展开即类型层面的加法

表达式 [...Prev, ...Curr] 之所以有效，是因为 TypeScript 的类型系统理解可变元组类型。若 Prev = [1, 1]，Curr = [1, 1, 1]，则 [...Prev, ...Curr] = [1, 1, 1, 1, 1]，其长度为 5。这实际上是在类型系统中计算了 2 + 3 = 5。

这个技巧可以推广：任意两个表示数字 A 和 B 的元组，都可以通过展开并读取长度来实现"相加"。相比逐个元素构建第三个元组，这是一种（在编译器角度）近乎零成本的操作。

总结

元组即数字：TypeScript 类型系统中所有算术问题都归结为同一套方案——用 1[] 元组表示数字，展开合并来相加，读取 .length 取出值。
三累加器模式（Index、Prev、Curr）可以清晰地将任何含多个状态变量的迭代算法映射为带默认类型参数的单个递归类型。
默认类型参数即初始状态：这是隐藏累加器参数、对外暴露简洁 API 的惯用做法——公开接口是 Fibonacci<T>，内部递归负责携带所有状态。
通过条件类型实现尾递归：条件类型的每个分支要么返回最终值，要么以更新后的参数继续递归，这与尾调用消除的思路一致，将递归深度控制在合理范围内。
边界条件：当题目是 1 索引时，从 1 而非 0 开始计数；确保初始 Prev/Curr 分别对应 fib(0) 和 fib(1)，这样对所有 T ≥ 1 的输入递归都能得到正确结果。