Recursion

Recursion

Recursion, in computer science is when a function calls itself. This may look confusing at first sight but can be very useful to solve certain types of problems.

Fibonacci Numbers

An example of a problem that can be solved by recursion is generation of Fibonacci numbers. Fibonacci numbers are the sequence of numbers: 0, 1, 1, 2, 3, 4, 5, 8, 13, … They are generated by adding the last two numbers in the fibonnaci sequence, other than the first two numbers which are 0 and 1.

0 and 1 are the base cases, the recursive function is not called in this case.

Lets take a look at one of the ways to solve this problem using code.

function fibonnaci(n) {
    if (n < 2) {
        return 1
    } else {
        return fibonnaci(n - 1) + fibonnaci(n - 2)
    }
} 

Press the run button below to see how the code runs. Each circle node is a function call and the edges represent what is returned by the function call. As the visualization shows a tree of function calls that are done when running the code fibonacci(4).