Explanation of recursion and fibonacci numbers

recursion.md

[[recursion and the stack]] #recursion

• Recursion is when a function calls itself.
• A recursive algorithm must have a base case, which is a state that tells the recursive function to stop calling itself and return a value

• fibonacci numbers

• The Fibonacci numbers are a sequence of integers in which the first two elements are 0 & 1, and each following elements are the sum of the two preceding elements:
• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ..., 233
• fibo(n) = fibo(n-1) + fibo(n-2)

Iterative

 function fibonacciLoop(nthNumber) {
        //use loop
        let previouspreviousNumber
        let previousNumber = 0
        let currentNumber = 1;

        for (int i = 1; i < nthNumber ; i++) {

            previouspreviousNumber = previousNumber;

            previousNumber = currentNumber;

            currentNumber = previouspreviousNumber + previousNumber;

        }
        return currentNumber;
    }  

Recursive

function fibonacciRecursion(nthNumber) {
        //use recursion
        if (nthNumber === 0) {

            return 0;

        } else if (nthNumber == 1) {

            return 1;
        }   
     return fibonacciRecursion(nthNumber - 1) + fibonacciRecursion(nthNumber - 2);
    }

What is happening?

• If you ask fibonacci for the 4th number, it calls itself to get the 3rd number and second number, and adds them together.
• it keeps calling itself until it reaches the base case, which in this case is fibonacci(0) and fibonacci(1) since we know we return 1 for this value. Always try to identify the base case.
• The higher numbers are "waiting" from the results of lower numbers, so after the base case returns, the stack "unwinds"
• fibonacci(4) is equal to fibonacci(3) + fibonacci(2)
• fibonacci(3) is equal to fibonacci(2) + fibonacci(1)
• fibonacci(2) is equal to fibonacci(1) + fibonacci(0)
• fibonacci(1) is equal to 1
• fibonacci(0) is equal to 1