The previous answer provided will run in exponential time instead of linear time. It also uses short-circuiting operators incorrectly.

int fib(int n){ if(n <= 1) return n; else return(fib(n-1) + fib(n-2)); }

def fib(n): a, b = 0, 1 while n: n -= 1 a, b = b, a+b return a O(n) time, O(1) space

function fibBottomUp(n, fib={}) { //O(n) fib[0] = 0; fib[1] = 1; let index = 2; while (index <= n){ fib[index] = fib[(index-1)] + fib[(index-2)]; index++; } return fib[n] }

public int fib(n) { if (n == 1 | n == 0) { return 1; } else { return fib(n-1)+fib(n-2); } }