Dynamic Programming
Non-Dynamic Programming O(2^n) Runtime Complexity, O(n) Stack complexity def fibonacci(n): if n < 2: return 1 return fibonacci(n-1) + fibonacci(n-2) This is the most intuitive way to write the problem. At most the stack space will be O(n) as you descend the first recursive branch making calls to fibonacci(n-1) until you hit the base case n < 2 . The O(2^n) runtime complexity proof that can be seen here: Computational complexity of Fibonacci Sequence. The main point to note is that the runtime is exponential, which means the runtime for this will double for every subsequent term, fibonacci(15) will take twice as long as fibonacci(14) . Memoized O(n) Runtime Complexity, O(n) Space complexity, O(n) Stack complexity memo = [] memo.append(1) # f(1) = 1 memo.append(1) # f(2) = 1 def fibonacci(n): if len(memo) > n: return memo[n] result = fibonacci(n-1) + fibonacci(n-2) memo.append(result) # f(n) = f(n-1) + f(n-2) return result With the memoized approach we introduce an array t...