Fibonacci Numbers
Write a function fib(n) that returns the nth Fibonacci number. The Fibonacci sequence is defined as F(n) = F(n-1) + F(n-2) with F(0) = 1 and F(1) = 1, which produces the following pattern:
1, 1, 2, 3, 5, 8, 13 ...
Examples
Pythonfib(0) # => 1 fib(1) # => 1 fib(2) # => 2 fib(3) # => 3 ... fib(10) # => 89 fib(20) # => 10946
The Fibonacci sequence is defined recursively since it refers to itself.
We can start with a recursive implementation and optimize it.
Each call to F(n) has two subproblems: F(n-1) and F(n-2). Can we memoize these calculations?
Does your solution work in O(n) time?
This question is a classic example of how dynamic programming, or memoization, can help us solve problems faster by reducing repetitive computations.
# Recursive implementation
def fib(n):
if n <= 1:
return 1
return fib(n-1) + fib(n-2)In this first version, we recursively call the fib function twice, and then we call it twice more in every subsequent recursive call, so the total number of operations expands to O(2^n)!
To improve the runtime of our program, let's save our prior calculations in a dictionary called memo and pass it into our function. Now, if we've already found fib(n) before, our function will use this stored value instead of recursing again.
# Recursive, memoized version
def fib(n, memo=None):
if n <= 1:
return 1
if memo is None:
memo = {}
if n not in memo:
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]Time Complexity: The time complexity of the memoized version is O(n). This is because each Fibonacci number from 0 to n is computed only once and then stored in the memo dictionary. The recursive calls will now simply look up the value in the dictionary if it has already been computed, reducing redundant calculations.
Space Complexity: The memo dictionary stores each Fibonacci number from 0 to n, which requires O(n) space.
Problem Statement: The Fibonacci sequence is defined as
F(n) = F(n-1) + F(n-2)withF(0) = 1andF(1) = 1.The solution is given in the problem statement itself.
Otherwise, return the sum of data at (n - 1) and (n - 2).
Explanation: The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, typically starting with 0 and 1.
Java Solution:
public static int fib(int n) { // Base Case 1 if(n == 0) { return 1; } // Base Case 2 if(n == 1) { return 1; } return fib(n - 1) + fib(n - 2); }