Fibonacci Sequence

Challenge Link

Challenge

Implement a generic Fibonacci<T> that takes a number T and returns its corresponding Fibonacci number.

The sequence starts: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

For example:

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

Solution

The core insight: TypeScript has no built-in arithmetic, but tuple lengths are numeric literal types. We can represent numbers as tuples of 1s and use spread + ["length"] to do addition.

For Fibonacci, we need to track three things simultaneously: the current position in the sequence, the previous value, and the current value. We advance these together through recursion, using a length-as-counter tuple to know when to stop.

type Fibonacci<
  T extends number,
  // Current position counter (starts at 1)
  Index extends 1[] = [1],
  // The "previous" Fibonacci value as a tuple
  Prev extends 1[] = [],
  // The "current" Fibonacci value as a tuple
  Curr extends 1[] = [1]
> = Index["length"] extends T
  ? Curr["length"]
  : Fibonacci<T, [...Index, 1], Curr, [...Prev, ...Curr]>

How it works step by step for Fibonacci<5>:

When Index["length"] === T, we return Curr["length"].

The transition at each step:

• Index grows by 1 (next position)
• New Prev = old Curr
• New Curr = old Prev + Curr (spread both tuples together)

Deep Dive

Why Tuples Instead of Numbers

TypeScript’s conditional types can check equality between types, but they cannot perform arithmetic on numeric literal types directly. 3 + 2 is not valid in type position. However, [...Array<1>, ...Array<1>]["length"] is perfectly valid — it spreads two tuples together and reads the resulting length as a numeric literal.

This is the foundational trick behind virtually all type-level math in type-challenges. Numbers become tuples; addition becomes tuple concatenation; “is this number N?” becomes Tuple["length"] extends N.

Three-State Accumulator Pattern

The classical Fibonacci function takes (prev, curr) and steps forward as (curr, prev + curr). Here we replicate exactly that logic but carry three states: Index (the countdown/position counter), Prev, and Curr. This “carry your accumulators as type parameters” pattern is the standard way to convert iterative algorithms into tail-recursive type-level functions.

TypeScript will evaluate these recursively — each “iteration” is a recursive type instantiation. The default recursion limit is ~1000 instantiations, which allows computing Fibonacci values for reasonably large T.

Why Default Parameters Start at [1] for Index

The Fibonacci sequence is 1-indexed in this challenge: Fibonacci<1> = 1, Fibonacci<2> = 1, Fibonacci<3> = 2, etc. By starting Index at [1] (length 1) and Curr at [1] (value 1), the base case Index["length"] extends T correctly returns 1 when T = 1 without any special-case handling.

Starting Prev at [] (empty tuple, length 0) means the first “step” produces Curr = [...[], ...[1]] = [1] — which is correct, since fib(2) = 1.

Tuple Spreading as Type-Level Addition

The expression [...Prev, ...Curr] works because TypeScript’s type system understands variadic tuple types. If Prev = [1, 1] and Curr = [1, 1, 1], then [...Prev, ...Curr] = [1, 1, 1, 1, 1], whose length is 5. This is genuinely computing 2 + 3 = 5 in the type system.

This technique generalizes: any pair of tuples representing numbers A and B can be “added” by spreading and reading length. It’s a constant-cost operation (from the compiler’s perspective) compared to building up a third tuple element-by-element.

Key Takeaways

• Tuples are numbers in TypeScript’s type system. Every type-level arithmetic problem reduces to: represent numbers as 1[] tuples, spread to add, and read .length to extract the value.
• The three-accumulator pattern (Index, Prev, Curr) cleanly maps any iterative algorithm with multiple state variables to a single recursive type with default type parameters.
• Default type parameters as initial state is the idiomatic way to hide accumulator parameters from callers — the public API is Fibonacci<T> while the internal recursion carries all the state.
• Tail recursion via conditional types: each branch of the conditional either returns a final value or recurses with updated parameters. This mirrors tail-call elimination, keeping the recursion depth bounded.
• Boundary conditions: start your index at 1 (not 0) when the problem is 1-indexed, and ensure your initial Prev/Curr values match fib(0) and fib(1) respectively so the recursion produces correct results for all T ≥ 1.