Easy Recursion
Fibonacci
Receives a non-negative integer n and returns the n-th Fibonacci number, where fib(0) = 0, fib(1) = 1, and every later term is the sum of the two before it (fib(k) = fib(k-1) + fib(k-2)). It computes the answer via top-down recursion: fib(n) calls fib(n-1) and fib(n-2), which in turn call their own smaller sub-problems, down to the base cases 0 and 1. A memo (a map from index to its already-solved value) records every sub-problem's result the first time it is solved, so a later call for the same index returns instantly instead of recomputing it — turning the naive exponential recursion into O(n) time and space. Returns the single integer fib(n); n ≤ 0 returns 0 directly, with no recursion.
Visualization
- Input
- Result
Algorithm code
// Fibonacci — a single pure function. Receives a non-negative integer n and
// returns the n-th Fibonacci number (fib(0) = 0, fib(1) = 1), computed via
// recursive decomposition (fib(n) = fib(n-1) + fib(n-2)) with memoization so
// each sub-problem is solved only once, in O(n) time and space.
/**
* @param {number} n - index into the Fibonacci sequence (0-based)
* @returns {number} the n-th Fibonacci number
*/
export function fibonacci(n) {
return n <= 0 ? 0 : fib(n, new Map());
}
function fib(k, memo) {
if (k <= 1) return k;
if (memo.has(k)) return memo.get(k);
const value = fib(k - 1, memo) + fib(k - 2, memo);
memo.set(k, value);
return value;
}FUNCTION fibonacci(n):
IF n <= 0:
RETURN 0
RETURN fib(n, empty map)
FUNCTION fib(k, memo):
IF k <= 1:
RETURN k
IF memo HAS k:
RETURN memo[k]
value ← fib(k - 1, memo) + fib(k - 2, memo)
memo[k] ← value
RETURN value