fibonacci in typescript

Here's how to implement the Fibonacci sequence in TypeScript using recursion:

index.ts
function fibonacci(n: number): number {
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}
122 chars
7 lines

However, this implementation is not very efficient as it computes the same sub-problems over and over again. To optimize it, we can use memoization.

Here's an implementation using memoization and an array:

index.ts
function fibonacci(n: number, memo: number[] = []): number {
  if (memo[n]) {
    return memo[n];
  }
  if (n <= 1) {
    return n;
  }
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}
217 chars
11 lines

The memo array stores the previously computed values, so we can reuse them instead of recomputing them.

To use this implementation, simply call the fibonacci function with the desired index:

index.ts
console.log(fibonacci(6)); // Output: 8
40 chars
2 lines

This will output the sixth number in the Fibonacci sequence, which is 8.