Nth Fibonacci
AlgoExpert Intro
The Fibonacci sequence is defined as follows: the first number in the sequence is 0, the second is 1, and the nth number is the sum of (n-1)th and (n-2)th numbers. Write a function that takes in an integer n and returns the nth Fibonacci number.
Important to note: the Fibonacci sequence is often defined with its first two numbers as F(0) = 0 and F(1) = 1. For the purposes of this question, the first Fibonacci number is F(0); therefore, getNthFib(1) is equal to F(0), getNthFib(2) is equal to F(1), and so on...
LeetCode Intro
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
Given n, calculate F(n).
Thoughts
It's important to note that the above two approaches differ slightly where the index starts. The LeetCode problem expects that the index starts at 0, meaning if we pass 0 we'll return what's in [0] if we were to think of the series of numbers as an array, where the AlgoExpert problem defines that the first value is equal to 0; meaning we are passing 1, not 0. This can be a gotcha and requires that we read the problem carefully. Also, since this problem traditionally focuses on recursion, I'll discuss that initially, then discuss approaching this problem in an iterative approach.
What is Recursion?
In computer science recursion is the process in which a function or algorithm called itself repeatedly until a particular condition is met at which time the rest of each repetition is processed from the last one called to the first. A common depiction would be Russian nesting dolls. Source
What is Iteration?
In iterative function or algorithm means that a series of instructions or code are repeated until a given condition is met. This usually appears as some form of a loop; for, while, etc.
What is a Call Stack?
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. We typically talk about this during recursion as each recursive call stores data on the call stack for the duration of the executing function. Once the function reaches the end of the recursion, the data is popped off of the call stack and processed. This is important to note as we evaluate space time complexity between the two approaches to solve this problem.
Approach in Go
Recursion
AlgoExpert
package main
func GetNthFib(n int) int {
if n == 1 {
return 0
} else if n == 2 {
return 1
}
return GetNthFib(n - 1) + GetNthFib(n - 2)
}
As you can see here, we've defined that getNthFib(1) shall return the value 0, and getNthFib(2) shall return the value 1. Then we proceed to the recursive part of the function where we return the sum of calling the function with n-1 and n-2. The recursion will eventually hit an end where 0 and 1 will be supplied and then it will work its way back up the call stack replacing each call to the function with an appropriate value until it hits the nth number in the sequence. It then returns that value.
LeetCode
func fib(n int) int {
if n == 0 {
return 0
} else if n == 1 {
return 1
}
return fib(n - 1) + fib(n - 2)
}
Not much is different here between the approach other than how we define the first number. Based on that we decrement the n values in the if conditions. The approach is the same. If ever you're doing this during an interview, you'll want to pay attention here or ask your interviewer. I've had this problem in the past, and fairly certain it resembled the LeetCode expectations.
Iterative
AlgoExpert
package main
func GetNthFib(n int) int {
ans := []int{0, 1}
if n == 1 {
return ans[0]
} else if n == 2 {
return ans[1]
}
for i := 3; i <= n; i++ {
nextFib := ans[0] + ans[1]
ans[0] = ans[1]
ans[1] = nextFib
}
return ans[1]
}
LeetCode
func fib(n int) int {
start := []int{0,1}
if n == 0 {
return start[0]
} else if n == 1 {
return start[1]
}
for i:=2; i <= n; i++ {
nextFib := start[1] + start[0]
start[0] = start[1]
start[1] = nextFib
}
return start[1]
}
With an iterative approach, we initialize an array on int type with the first two values of the Fibonacci sequence; 0 and 1. We then define the same conditional statements we saw in the recursion solution. If neither condition are met, we move on. We start the index i where 2 ahead of where our conditions were set. You'll notice that since we started with 1 on the AlgoExpert problem, we started our loop index at 3. Similarly, with the LeetCode problem we start with 0, so we set our loop index to 2. In each iteration of the loop, we initialize a loop local variable with the sum of what is currently in the array. We then set index [0] of the array equal to the value in index [1] of the array, effectively pushing the value left and then we set the value at index [1] to the variable value that we initialized at the beginning of the loop. We then increment i until we we meet the condition of the loop and exit. We return the value at index [1].
Space Time Complexity
Recursive approach
For the recursive approach we are looking at a time complexity of O(2^N), where N is the value we are looking for. This means the larger the value is for N the longer the time to completion will take, and since we call the function twice on each call it ends up 2 to the power on N. For space complexity we are looking at O(N). Although we aren't explicitly storing data inside, we are storing data on the call stack (mentioned earlier), so we are still making use of memory here.
Iterative approach
For the iterative solution, we are looking at a time complexity of O(N). Again, N is defined as the value we are looking for. The larger the number, the larger the increase in duration when we execute the function. Also, our array operations were constant time, since we accessed indexes explicitly and didn't have to search. For space complexity, we drop it down to constant time, or O(1), since we store the same amount of data in our array throughout the entire execution of the function.