find the nth lucas number in typescript

To find the nth Lucas number in TypeScript, there are various approaches available. Here, we will discuss two methods:

Method 1: Recursion with memoization

The first approach is to use recursion with memoization. Recursion is a programming technique where a function calls itself recursively and memoization is an optimization technique where a function stores the results of expensive function calls and returns the cached results when the same inputs occur again.

index.ts
function nthLucasNumber(n: number, memo: number[] = []): number {
  if (n == 0) {
    return 2;
  }
  if (n == 1) {
    return 1;
  }
  if (memo[n] != null) {
    return memo[n];
  }
  return memo[n] = nthLucasNumber(n - 1, memo) + nthLucasNumber(n - 2, memo);
}
263 chars
13 lines

In this implementation, the nthLucasNumber function takes two arguments: n, which is the index of the Lucas number to be found, and memo, which is an array used for memoization. The memo array is initialized with empty values which will be populated as the function progresses through recursion.

Method 2: Iteration with dynamic programming

The second approach is to use iteration with dynamic programming. It involves building an array of Lucas numbers iteratively by storing the previously computed values in an array.

index.ts
function nthLucasNumber(n: number): number {
  if (n == 0) {
    return 2;
  }
  if (n == 1) {
    return 1;
  }
  let lucas: number[] = [2, 1];
  for (let i = 2; i <= n; i++) {
    lucas[i] = lucas[i - 1] + lucas[i - 2];
  }
  return lucas[n];
}
247 chars
14 lines

In this implementation, the nthLucasNumber function takes one argument n which is the index of the Lucas number to be found. It initializes an array lucas with the first two Lucas numbers and then iteratively computes the remaining numbers using dynamic programming.

Both the methods can be used to find the nth Lucas number in Typescript.