Recursion and dynamic programming

by María Fernández

HTML

<div>
   <p>Fibonacci (normal recursive): <span id="fibonacci"></span></p>
   <p>Fibonacci (optimized): <span id="fibonacci-opti"></span></p>
   <p>Triple steps: <span id="triple-steps"></span></p>
   <p>Triple steps (optimized): <span id="triple-steps-opti"></span></p>
   <p>String perms: <span id="permutations"></span></p>
</div>

JavaScript

// Fibo normal: no values cached.
// Time complexity is O(2^n) since for each number we have 2
// recursive calls to the stack. It takes over 1s to compute 40th fibo
// number!! No good...
function fibonacciNormal(n) {
	if (n === 0 || n === 1) return n;
	return fibonacciNormal(n - 1) + fibonacciNormal(n - 2);
}
const n = 40;
const t1 = performance.now();
const fibo = fibonacciNormal(n);
const t2 = performance.now();
document.getElementById('fibonacci').innerHTML =
	`of ${n} is ${fibo}. It took ${t2 - t1} ms.`;

// Fibo optimized, we cache results that will be used later
// Time complexity is O(n). It takes fraction of miliseconds
// to calculate Fibo of way bigger numbers, like 1000.
// It still could be more optimized in terms of space:
// in a bottom-up approach (1st get Fib(0) & Fib(1), then you
// can calculate 2, etc), we only need the last two Fibonacci values
// computed, so we could just have 2 variables for them instead of
// saving the whole array of results.
function fibonacciOptimized(n) {
	let memo = {};
	return fibonacciOptimizedRecursive(n, memo);
}

function fibonacciOptimizedRecursive(n, memo) {
	if (n === 0 || n === 1) return n;
  if (!memo[n]) {
  	memo[n] = fibonacciOptimizedRecursive(n - 1, memo) +
    	fibonacciOptimizedRecursive(n - 2, memo);
  }
  return memo[n];
}
const nOpti = 1000;
const t1Opti = performance.now();
const fiboOpti = fibonacciOptimized(nOpti);
const t2Opti = performance.now();
document.getElementById('fibonacci-opti').innerHTML =
	`of ${nOpti} is ${fiboOpti}. It took ${t2Opti - t1Opti} ms.`;
  
// Triple step: a kid is running up a staircase (n steps) and can hop
// either 1, 2 or 3 steps at a time. Implement a method to count how many
// possible ways the kid can run up the stairs
// Top-down approach: The last step the kid did reached the top, and
// it could have been 1/2/3 steps at a time, each "branch" constitutes a way
// to go up the stairs. So from that do recursion to figure out how many
// possibilities there...