Skip to content

Instantly share code, notes, and snippets.

@SaltyAom
Last active June 3, 2025 13:00
Show Gist options
  • Save SaltyAom/da8b28b1abb13d3edb9ae9d1e86298db to your computer and use it in GitHub Desktop.
Save SaltyAom/da8b28b1abb13d3edb9ae9d1e86298db to your computer and use it in GitHub Desktop.
Fibonacci Sequence in TypeScript type
// 1st attempt
type Arr<
T extends number,
Carry extends number[] = []
> = Carry['length'] extends T ? Carry : Arr<T, [0, ...Carry]>
type Add<A extends number, B extends number> = [...Arr<A>, ...Arr<B>]['length']
type Subtract<A extends number, B extends number> =
Arr<A> extends [...Arr<B>, ...infer R] ? R['length'] : 0
type Compute<
Target extends number,
Sequence extends number[] = [0, 1]
> = Sequence['length'] extends Target
? Sequence extends [...infer R, infer Last]
? Last
: never
: Compute<
Target,
// @ts-ignore
[
...Sequence,
Add<
Sequence[Subtract<Sequence['length'], 1>],
Sequence[Subtract<Sequence['length'], 2>]
>
]
>
type Fibonacci<Target extends number> = Target extends 0
? 0
: Target extends 1
? 1
: // @ts-ignore
Compute<Add<Target, 1>>
type A = Fibonacci<17>
// 2nd attempt
type Compute<
Limit extends number,
Sequence extends number[][] = [[0], [0]]
> = Sequence['length'] extends Limit
? Sequence extends [...any, infer Last extends any[]]
? Last['length']
: 0
: Sequence extends [...any, infer A extends any[], infer B extends any[]]
? Compute<Limit, [...Sequence, [...A, ...B]]>
: never
type Fibonacci<Target extends number> = Target extends 0
? 0
: Target extends 1
? 1
: Compute<Target>
type A = Fibonacci<20>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment