Finding the Nth Fibonacci number
Recursion & memoization
The Fibonacci sequence is the series of numbers starting from 0, 1 where each consecutive number N is the sum of the two previous numbers.
It goes…
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 31781…
Given a place in the sequence, how can we find the value of N?
This is Where Recursion Comes In
Recursion is a programming paradigm in which a function calls on itself. Here is an example of a recursive function.
function factorial(n) {
if (n === 0) return 1
return n * factorial(n - 1)
}// factorial(5) => 5 * 4 * 3 * 2 * 1
As you might expect, recursive functions are usually written with a “base case” (n === 0) at which the function stops calling on itself.
We Can Find (N) Recursively
As we said before, the value of a number in the Fibonacci sequence is equal to the sum of the previous two numbers. The only exceptions are the first two numbers, because they are proceeded by 1 or fewer numbers.
We can write an algorithm that finds N iteratively (by starting from 0 and following this pattern until reaching N and returning its value), but, for the sake of this example, let’s try our first recursive function.
function fibonacci(N) {
if (N < 2) {
return N
}
else {
return fibonacci(N-1) + fibonacci(N-2)
}
}When we call fibonacci(4), the return value we evaluate is fibonacci(3) + fibonacci(2).
fibonacci(4) returns (fibonacci(3) + fibonacci(2))
fibonacci(3) is fibonacci(2) + fibonacci(1)
fibonacci(2) is fibonacci(1) + fibonacci(0)
fibonacci(1) is 1.
fibonacci(0) is 0.The return statement can be simplified to (1 + 1) + (1 + 0) = 3, or, when N = 4, the number 3 is the Nth number from 0 in the Fibonacci sequence.
Memoization Can Make Our Solution More Memory Efficient
Even in the above example, for N=4, we computed the same value more than once. We can reduce the amount of computations our program needs to make by caching the values.
Memoization is when a computation caches its results in an object for future reference.
In this example, I will use an object to store Fibonacci numbers that have already been computed. This allows our function to run in O(n) time, because every possible number needs only to be calculated once.
let fibonacciSequence = {}function fibonacciOptimized(N) {
let val
if (fibonacciSequence[N]) {
val = fibonacciSequence[N]
}
if (N < 2) {
val = N
}
else {
val = fib(N-1) + fib(N-2)
}
fibonacciSequence[N] = val
return val
};
Should You Use Recursion?
Just because a function can be written recursively doesn’t mean it should be. This article goes into further detail about the performance of recursive vs. iterative functions, including recursive tail call and trampoline optimizations.
Resources
For further reading and practice.
