Recursion - Fibonacci Sequence

A function is said to be recursive when it calls itself until it hits a defined stopping point. Recursion allows you to write functions in a "cleaner" way. While the code looks cleaner, one issue with recursion is that it can slow down functionality. As a programmer you have to try to find the right balance between speed and elegance.

Examples:

A common example of recursion is finding the nth number in the fibonacci sequence.For reference the fibonacci sequence is a sequence of number starting from 0 and 1 such that each number is the sum of the two preceding ones.

function fib(n) {
  if (n < 2) {
    return 1;
  }
  return fib(n -1) + fib(n -2);
}

Lets break this down:

• Stopping point/ base case: this is the conditional statement that will stop the function from calling itself.

  if (n < 2) {
    return 1;
  }

• The recursive part: where the function is called

return fib(n - 1) + fib(n - 2);

• fib(5) breaks down to:

The function will call itself until it hits a base case and then add up the bottom branches to give you 5.

Time Complexity:

The Big O of this recursive function is exponential (2^N) becuase the size of the tree grows exponentially when N grows.