Skip to content

Instantly share code, notes, and snippets.

@zzarcon
Created February 17, 2016 21:17
  • Star 5 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save zzarcon/d4bea4fb85f317fe8fc1 to your computer and use it in GitHub Desktop.
Javascript Fibonacci memoization
function fibonacci(num, memo) {
memo = memo || {};
if (memo[num]) return memo[num];
if (num <= 1) return 1;
return memo[num] = fibonacci(num - 1, memo) + fibonacci(num - 2, memo);
}
@hozefaj
Copy link

hozefaj commented Feb 6, 2017

👍

@aboglioli
Copy link

In line 5 it should be:

if (num <= 1) return num;

@wdiasvargas
Copy link

wdiasvargas commented Jun 20, 2017

@syedwshah
Copy link

syedwshah commented Dec 6, 2020

TS Fibonacci memoization

interface Memo {
  [key: number]: number;
}

//Cache
const cacheMeOusside: Memo = {};

const fib = (num: number, memo: Memo): number => {
  if (num < 0) {
    return 0;
  }
  else if (num <= 1) {
    memo[num] = num;
    return memo[num];
  }
  
  if (memo[num]) {
    return memo[num];
  }

  return fib(num - 1, memo) + fib(num - 2, memo);
}

// Sample output
const cache: Memo = cacheMeOusside;
for (let i = 0; i <= 10; i++) {
  cache[i] = fib(i, cacheMeOusside);
}
console.log(cache);

Output:

{ '0': 0,
  '1': 1,
  '2': 1,
  '3': 2,
  '4': 3,
  '5': 5,
  '6': 8,
  '7': 13,
  '8': 21,
  '9': 34,
  '10': 55 }

https://github.com/syedwshah/fibonacci_memoization.ts
https://repl.it/@SyedShah7/CoarseUnsteadyMethod#index.ts

Personally, I think this is better:

interface Memo {
  [key: number]: number;
}

//Cache of fibonacci sequence
const cacheMeOusside: Memo = {
  0: 0,
  1: 1
};

const fib = (num: number, memo: Memo): number => {
  if (num < 0) {
    return 0;
  }
  
  if (memo[num]) {
    return memo[num];
  }

  return fib(num - 1, memo) + fib(num - 2, memo);
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment