Fibonacci Sequence

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

Zur Lösung dieses Problems können wir variadic tuple types nutzen. Wir definieren drei Akkumulatoren, um die vorherige Zahl, die aktuelle Zahl, sowie den Index / Fortschritt zu erfassen. Anschließend addieren wir in jeden Aufruf des Typen den aktuellen Wert von der ersten und zweiten Zahl, und inkrementieren den Index. Danach wird der Typ erneut so lange aufgerufen, bis wir die Fibonacci Zahl mit dem Index erreicht haben:

type Fibonacci<
  T extends number,
  // Vorherige Zahl
  One extends number[] = [1],
  // Aktuelle Zahl
  Two extends number[] = [1],
  // Index, um die Anzahl der Aufrufe zu erfassen
  Index extends any[] = [1]
> = Index["length"] extends T
  ? One["length"]
  : Fibonacci<T, Two, [...One, ...Two], [...Index, 1]>;

Challenge

Solution

References