CODE EXAMPLE FOR JAVASCRIPT

fibonacci recursion

function fib(n) {
    if (n === 1 || n === 0)
        return n

    return fib(n - 1) + fib(n - 2)
}
console.log('fib:', fib(9))		// [Log]: fib: 34
// Time complexity O(2^n)
// Space complexity O(n)
// Since fib(n-1) gets evaluated completely before fib(n-2), there will never be more than n levels of recursion.