## Python

`O(2^n)`

``````def fibb(n):
if n == 1 or n == 0:
return n
else:

assert fibb(0) == 0; assert fibb(1) == 1, fibb(1); assert fibb(2) == 1, fibb(2);
assert fibb(3) == 2, fibb(3); assert fibb(4) == 3, fibb(4); assert fibb(5) == 5, fibb(5);
assert fibb(6) == 8, fibb(6); assert fibb(7) == 13, fibb(7); assert fibb(8) == 21, fibb(8);
assert fibb(9) == 34, fibb(9); assert fibb(10) == 55, fibb(10)
``````

Variation:

``````def fibb(n):
return n if (n <= 1) else fibb(n - 2) + fibb(n - 1)

``````

Memoized version `O(n)`:

``````def fibb(n, mem={}):
if n == 1 or n == 0:
return n

if not mem.get(n):
mem[n] = fibb(n - 2) + fibb(n - 1)

return mem[n]

``````

## Javascript

#2021.07.22

``````function fibb(n) {
if (n <= 1) {
return n;
}

const addend1 = n - 1;
const addend2 = n - 2;

}

assert.equal(fibb(0), 0); assert.equal(fibb(1), 1); assert.equal(fibb(2), 1); assert.equal(fibb(3), 2);
assert.equal(fibb(4), 3); assert.equal(fibb(5), 5); assert.equal(fibb(10), 55);
``````

Variation:

``````function fibb(n) {
return (n <= 1) ? n : fibb(n - 1) + fibb(n - 2);
}

assert.equal(fibb(0), 0); assert.equal(fibb(1), 1); assert.equal(fibb(2), 1); assert.equal(fibb(3), 2);
assert.equal(fibb(4), 3); assert.equal(fibb(5), 5); assert.equal(fibb(10), 55);
``````