// 你的答案
type Fibonacci<T extends number, N extends any[] = [null], Current extends any[] = [null], Prev extends any[] = []> = 
  N['length'] extends T ? Current['length'] : Fibonacci<T, [...N, null], [...Current, ...Prev], Current>

Solution by heyuelan #34720

// 递减
type Decrement<T extends number, U extends any[] = []> = U['length'] extends T ? 
  U extends [infer _, ...infer Rest] ? 
    Rest['length'] 
  : 
    never 
: 
  Decrement<T, [unknown, ...U]>;
// 累加
type Add<A extends number, B extends number,L extends number[] = []> = A extends 0 ? B extends 0 ? L['length'] : Add<A,Decrement<B>,[...L,1]>  : Add<Decrement<A>,B,[...L,1]> 

type Fibonacci<T extends number, F extends number = 1,S extends number = 1, L extends number[] = []> = T extends 1 | 2 ? 
  1 
: 
  L['length'] extends Decrement<T> ? F :  Fibonacci<T, S, Add<F,S>,[...L,1]>

Solution by Zhang-LuBin #34206

type BuildArray<
	T extends number,
	SUM extends unknown[] = []
> = T extends SUM['length'] ? SUM : BuildArray<T, [...SUM, unknown]>
type Add<N1 extends number, N2 extends number> = [
	...BuildArray<N1>,
	...BuildArray<N2>
]['length'] & number

type Fibonacci<
	T extends number,
	I1 extends number = 1,
	I2 extends number = 1,
	S extends unknown[] = [unknown,unknown]
> = T extends 1
	? I1
	: T extends S['length']
	? I2
  : Fibonacci<T, I2, Add<I1, I2>, [...S, unknown]>

Solution by WAGFS #34087

type Fibonacci<T extends number, CurIdx extends number[] = [1], Prev extends number[] = [], Cur extends number[] = [1]> = CurIdx['length'] extends T ? Cur['length'] :
Fibonacci<T, [...CurIdx, 1], Cur, [...Prev, ...Cur]>

Solution by ouzexi #34067

type Fibonacci<
  T extends number, 
  Pre extends number[] = [],
  Cur extends number[] = [1],
  Index extends number[] = [1]
> = T extends Index['length'] ? Cur['length'] : Fibonacci<T, Cur, [...Pre, ...Cur], [1, ...Index]>;

Solution by ZhipengYang0605 #33404

type Fibonacci<
  T extends number,
  U extends number[] = [1], 
  PRE extends number[] = [],
  SUF extends number[] = [1],
> = U['length'] extends T
  ? U extends [...infer _, infer Last]
    ? Last
    : never
  : Fibonacci<T, [...U, [...SUF, ...PRE]['length']], SUF, [...PRE, ...SUF]>; 

Solution by Shaocang #31748

// your answers

type NumToArr<T extends number, A extends number[] = []> = A["length"] extends T
  ? A
  : NumToArr<T, [...A, 0]>;
type MergeArr<A extends number[], B extends number[]> = [...A, ...B];
type Add<
  A extends number,
  B extends number,
  Res = MergeArr<NumToArr<A>, NumToArr<B>>
> = Res extends any[] ? Res["length"] : 0;
type GetLastItem<T extends any[]> = T extends [...infer R, infer L] ? L : never;
type GetBeforeLastItem<T extends any[]> = T extends [
  ...infer R,
  infer T1,
  infer T2
]
  ? T1
  : never;
type Fibonacci<T extends number, Rec extends any[] = [1, 1, 2]> = T extends 1
  ? 1
  : T extends 2
  ? 1
  : Rec["length"] extends T
  ? GetLastItem<Rec>
  : Fibonacci<T, [...Rec, Add<GetLastItem<Rec>, GetBeforeLastItem<Rec>>]>;

Solution by chenqy-yh #31231

type Fibonacci<T extends number, CurrentIndex extends any[] = [1], Prev extends any[] = [], Current extends any[] = [1]> = CurrentIndex['length'] extends T
  ? Current['length']
  : Fibonacci<T, [...CurrentIndex, 1], Current, [...Prev, ...Current]>

Solution by MyeonghoonNam #31063

type Fibonacci<T extends number, Current extends never[] = [never, never, never], Minus1 extends never[] = [never], Minus2 extends never[] = [never]> = 
  T extends 1 | 2
    ? 1
    : Current['length'] extends T
      ? [...Minus1, ...Minus2]['length']
      : Fibonacci<T, [never, ...Current], [...Minus1, ...Minus2], Minus1>

Solution by GodAraden #30797

type Push<T extends any[], U> = T extends [infer F, ...infer O] ? [F, ...O,  U] : [U];

type NumberToArray<T extends number, U extends any[] = []> = U['length'] extends T ?
  U : NumberToArray<T, Push<U, 0>>

type MinusOne<T extends number> = NumberToArray<T> extends [infer F, ...infer O] ? O['length'] : never;

type Plus<T extends number, U extends number> = [...NumberToArray<T>, ...NumberToArray<U>]['length']

type Fibonacci<T extends number> = T extends 1
  ? 1
  : T extends 2
    ? 1
    : Plus<Fibonacci<MinusOne<MinusOne<T>>>, Fibonacci<MinusOne<T>>>

Solution by 8471919 #30236

为什么这么写不对？

type Plus<A extends number, B extends number, AA extends any[] = [], BB extends any[] = []> =
    AA['length'] extends A ?
        BB['length'] extends B ?
            [...AA, ...BB]['length']:
            Plus<A, B, AA, [...BB, 0]>:
        Plus<A, B, [...AA, 0], BB>;


type plus = Plus<4, 5>;
const p: plus = 3;

type Fibonacci<T extends number, A extends number = 1, B extends number = 1> =
    T extends 0 ? A :
        Fibonacci<MinusOne<T>, Plus<A, B>, A>;

type Fib = Fibonacci<4>;

Solution by sundial-dreams #29500

type Fibonacci<
  T extends number,
  Cur extends number[] = [1],
  Prev extends number[] = [],
  Index extends number[] = [1]
> = Index["length"] extends T
  ? Cur["length"]
  : Fibonacci<T, [...Prev, ...Cur], Cur, [...Index, 1]>;

Solution by DoubleWoodLin #28736

// 你的答案
// type 中数字的累加往往利用[]进栈，在通过['length']实现累增计数操作
// 递归的2个基本条件
1.出口
2.递归表达试

type Fibonacci<
  T extends number,
  U extends any[] = [1],
  S1 extends any[] = [],
  S2 extends any[] = [1],
  SUM extends any[] = [1],
> = T extends U['length']
  ? S2['length']
  : Fibonacci<T, [...U, 1], [...S2], [...S1, ...S2], [...SUM, ...S1, ...S2]>

Solution by xpbsm #28456

type Pop<T extends number[]> = T extends [...infer Head, any] ? Head : never;

type MinusOne<
  N extends number,
  Acc extends number[] = []
> = Acc["length"] extends N ? Pop<Acc>["length"] : MinusOne<N, [...Acc, 0]>;

type MinusTwo<N extends number> = MinusOne<MinusOne<N>>;

type PlusTwo<
  N1 extends number,
  N2 extends number,
  Acc1 extends number[] = [],
  Acc2 extends number[] = []
> = Acc1["length"] extends N1
  ? Acc2["length"] extends N2
    ? [...Acc1, ...Acc2]["length"]
    : PlusTwo<N1, N2, Acc1, [...Acc2, 0]>
  : PlusTwo<N1, N2, [...Acc1, 0], Acc2>;

type Fibonacci<T extends number> = T extends 1
  ? 1
  : T extends 0
  ? 0
  : PlusTwo<Fibonacci<MinusOne<T>>, Fibonacci<MinusTwo<T>>>;

Solution by idebbarh #28441

// 你的答案
type ParseInt<T extends string> = T extends `${infer F extends number}` ? F : never;
// 反转
type ReverseString<T extends string> = T extends `${infer F}${infer R}` ? `${ReverseString<R>}${F}` : T;
// 移除头部 0
type RemoveLeadingZero<T extends string> = T extends '0' ? T : T extends `${'0'}${infer R}` ? RemoveLeadingZero<R> : T;
// 减一
type InternalMinusOne<T extends string> = T extends `${infer F extends number}${infer R}`
  ? F extends 0
  ? `9${InternalMinusOne<R>}`
  : `${[9, 0, 1, 2, 3, 4, 5, 6, 7, 8][F]}${R}`
  : never;

type MinusOne<T extends number> = T extends 0 ? -1 : ParseInt<RemoveLeadingZero<ReverseString<InternalMinusOne<ReverseString<`${T}`>>>>>

// 1 1 2 3 5 8 13 21
type Plus<F, S, R extends any[] = [], FN extends any[] = [], SN extends any[] = []> = FN['length'] extends F
? SN['length'] extends S
  ? R['length']
  : Plus<F, S, [...R, 0], FN, [...SN, any]>
: Plus<F, S, [...R, 0], [...FN, any]>

type Fibonacci<T extends number> = T extends 2 | 1
? 1 : Plus<Fibonacci<MinusOne<T>>, Fibonacci<MinusOne<MinusOne<T>>>>;

Solution by ixiaolong2023 #27835

type numberToArr<T extends number, U extends Array<any> = []> = U['length'] extends T ? U : numberToArr<T, [...U, any]>
type Add<T extends number, U extends number> = [...numberToArr<T>, ...numberToArr<U>]['length']

type Fibonacci<T extends number, U extends number = 3, Z extends any[] = [any], Y extends any[] = [any]> = T extends 1 ? 1 : T extends 2 ? 1 : 
  T extends U ? [...Z, ...Y]['length'] : Add<U, 1> extends number ?  Fibonacci<T, Add<U, 1>, [...Z, ...Y], Z> : -1

Solution by workkk98 #27372

// 你的答案

type Fibonacci<T extends number,L extends any[] = [],R extends any[] = [1],S extends any[] = []> = ${T} extends -${infer Z} ? 0 : [1,...S]['length'] extends T ? R['length'] : Fibonacci<T,R,[...L,...R],[1,...S]>

Solution by biubiuWang931111 #27266

// type Fibonacci<T extends number> = T extends 0 ? 0 : T extends 1 ? 1 : T extends 2 ? 1 : Fibonacci<T-1> + Fibonacci<T-2>

Solution by jsujeong #27037

type Fibonacci<T extends number, Index extends any[] = [1], Prev extends any[] = [], Curr extends any[] = [1]> =
  Index['length'] extends T ? Curr["length"] : Fibonacci<T, [...Index, 1], Curr, [...Curr, ...Prev]>

Solution by smileboyi #26994

// your answers

type Fibonacci<T extends number, Index extends number[] = [1], Prev extends number[] = [], Current extends number[] = [1]> =
Index['length'] extends T 
  ? Current['length']
  : Fibonacci<T, [...Index, 1], Current, [...Prev, ...Current]>

Solution by hhk9292 #26924

type Fibonacci<T extends number, Acc extends never[][] = [[never], [never]]>
  = T extends 0 ? 0
    : T extends 1 ? 1
      : Acc['length'] extends T
        ? Acc[0]['length']
        : Fibonacci<T, [[...Acc[0], ...Acc[1]], ...Acc]>

Solution by tokyo9pm #26732

type Fibonacci<T extends number,arr extends number[] = [1],num1 extends number[] = [],num2 extends number[] = [0]> = T extends 1 ? 1 : [...arr,0]['length'] extends T ? [...num1,...num2]['length'] : Fibonacci<T,[...arr,0],num2,[...num2,...num1]>

Solution by WangZiChu199910252255 #26598

type Length<T extends any[]> = T['length'];
type Push<T extends any[], V> = [...T, V];
type NTuple<N extends number, T extends any[] = []> = Length<T> extends N ? T : NTuple<N, Push<T, any>>;

type Sub<N1 extends number, N2 extends number> = NTuple<N1> extends [...NTuple<N2>, ...infer Rest] ? Length<Rest> : never;
type Add<N1 extends number, N2 extends number> = Length<[...NTuple<N1>, ...NTuple<N2>]>;


type Fibonacci<T extends number> = 
  T extends 1 ?
  1 :
  T extends 2 ?
  1 :
  Add<Fibonacci<Sub<T, 1>>, Fibonacci<Sub<T, 2>>>

Solution by kakasoo #26578

// 你的答案
type FIArray<T extends number> = T extends 1
  ? [1]
  : T extends 2
    ? [1]
    : [...FIArray<MinusOne<T>>, ...FIArray<MinusOne<MinusOne<T>>>]
type Fibonacci<T extends number> = FIArray['length']

Solution by adoin #26223

 type Tuple<T extends number, R extends Array<1> = []> = R['length'] extends T
  ? R
  : Tuple<T, [...R, 1]>;

type MinusOne<T extends number, R = Tuple<T>> = R extends [infer Head, ...infer Tail]
    ? Tail['length']
    : never;

type Add<T extends number, K extends number> = [...Tuple<T>, ...Tuple<K>]['length'];

type Fibonacci<T extends number> = T extends 0
  ? 0
  : T extends 1
    ? 1
    : Add<Fibonacci<MinusOne<MinusOne<T>>>, Fibonacci<MinusOne<T>>>;

Solution by yungo1846 #25641

// 你的答案
type Fibonacci<
  T extends number,                     // Target depth
  Cur extends unknown[] = [],           // Current array
  Prev extends unknown[] = [unknown],   // Previous array
  Count extends unknown[] = []          // Count our current depth
> = Count['length'] extends T ?
      Cur['length'] :
      Fibonacci<
        T,
        [...Cur, ...Prev],
        Cur,
        [unknown, ...Count]
      >

Solution by kiki-zjq #25219

4182 - Fibonacci Sequence

Implementing the Fibonacci sequence in TypeScripts type system... well... this one is a bit of a brain buster. The good news is, though, that if you manage to not crash TypeScript constantly while you develop it, the solutions are pretty fun to explore. I won't fault you for just watching this one instead of trying first, haha.

🎥 Video Explanation

🔢 Code

// ============= Test Cases =============
import type { Equal, Expect } from './test-utils'

type A1 = Fibonacci<1>;
type B1 = 1;
type C1 = Expect<Equal<A1, B1>>;

type A2 = Fibonacci<2>;
type B2 = 1;
type C2 = Expect<Equal<A2, B2>>;

type A3 = Fibonacci<3>;
type B3 = 2;
type C3 = Expect<Equal<A3, B3>>;

type A4 = Fibonacci<8>;
type B4 = 21;
type C4 = Expect<Equal<A4, B4>>;

// Input:  0, 1, 2, 3, 4, 5, 6,  7,  8,  9, 10, 12, ...
// Output: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

// ============= Your Code Here =============
type Fibonacci<
  T extends number,
  CurrentIndex extends any[] = ['🧮'],
  Prev extends any[] = [],
  Current extends any[] = ['🧮']
> =
  CurrentIndex['length'] extends T
  ? Current['length']
  : Fibonacci<
      T,
      [...CurrentIndex, '🧮'],
      Current,
      [...Prev, ...Current]
    >;

// ============== Alternatives ==============
// credit @NtsDK
type Fibonacci<
  T extends number,
  Result extends '🧮'[][] = [['🧮'], ['🧮']]
> =
  T extends 1 | 2
  ? 1
  : T extends Result['length']
    ? Result[0]['length']
    : Fibonacci<T, [
        [
          ...Result[0],
          ...Result[1]
        ],
        ...Result
      ]>;

type Fibonacci<
  T extends number,
  U extends unknown[] = ['🧮'],
  V extends unknown[] = [],
  W extends unknown[] = ['🧮']
> =
  W['length'] extends T
  ? U['length']
  : Fibonacci<
      T,
      [...U, ...V],
      U,
      ['🧮', ...W]
    >;

// credit: @ethereal-sheep
type Arrayify<N, Acc extends '🧮'[] = []> =
  Acc['length'] extends N
  ? Acc
  : Arrayify<N, ['🧮', ...Acc]>;
type Add<L, R> =
  [...Arrayify<L>, ...Arrayify<R>]['length'];
type Subtract<
  L,
  R,
  Acc extends '🧮'[] = []
> =
  L extends R
  ? Acc['length']
  : Subtract<L, Add<R, 1>, ['🧮', ...Acc]>;
type Fibonacci<T> = 
  T extends 0
  ? 0
  : T extends 1
    ? 1
    : Add<
        Fibonacci<Subtract<T, 2>>,
        Fibonacci<Subtract<T, 1>>
      >;

➕ More Solutions

For more video solutions to other challenges: see the umbrella list! https://github.com/type-challenges/type-challenges/issues/21338

Solution by dimitropoulos #24324

type NumberToTuple<T extends number, A extends unknown[] = []> =
  A['length'] extends T ? A : NumberToTuple<T, [...A, unknown]>

type ToNumber<T extends any[]> = T['length']

type Add<T extends number, U extends number> =
  ToNumber<[...NumberToTuple<T>, ...NumberToTuple<U>]>

type MinusOne<T extends number, Res extends unknown[] = NumberToTuple<T>> =
  Res extends [unknown, ...infer R]
    ? R['length']
    : never

type Fibonacci<T extends number> =
  T extends 0
    ? 0
    : T extends 1
      ? 1
      : Add<Fibonacci<MinusOne<MinusOne<T>>>, Fibonacci<MinusOne<T>>>

Playground

Solution by dowdiness #23964

type Fibonacci<T extends number,
  _Pre extends 1[] = [],
  _After extends 1[] = [1],
  _Counter extends 1[] = [1]> = _Counter[`length`] extends T ? _After[`length`]/*return*/ :
  Fibonacci<T, [..._After], [..._Pre, ..._After], [..._Counter, 1]>;

// old way
// type FibonacciSequence<T extends any[], U extends any[], I extends number, _Counter extends any[] = [true]> = I extends _Counter["length"] ? [...T, ...U]["length"] : (FibonacciSequence<[...U], [...T, ...U], I, [..._Counter, true]>);
// type Fibonacci<T extends number> = FibonacciSequence<[true], [], T>;

Solution by E-uler #23942

type Fibonacci<T extends number, A extends unknown [] = [1], B extends unknown[] = [], Index extends unknown [] = []> = Index['length'] extends T ? B['length'] : Fibonacci<T, B, [...A, ...B], [...Index, 1]>

Solution by asurewall #23175