VietMX Staff asked 3 years ago
Recursive solution looks pretty simple (see code).
Let’s look at the diagram that will help you understand what’s going on here with the rest of our code. Function fib is called with argument 5:
Basically our fib function will continue to recursively call itself creating more and more branches of the tree until it hits the base case, from which it will start summing up each branch’s return values bottom up, until it finally sums them all up and returns an integer equal to 5.
In case of recursion the solution take exponential time, that can be explained by the fact that the size of the tree exponentially grows when n increases. So for every additional element in the Fibonacci sequence we get an increase in function calls. Big O in this case is equal to O(2n). Exponential Time complexity denotes an algorithm whose growth doubles with each addition to the input data set.
function fib(n) { if (n < 2){ return n } return fib(n - 1) + fib (n - 2)}