Recursion

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function.

Recursive algorithm is essential to divide and conquer paradigm, whereby the idea is to divide bigger problems into smaller subproblems and the subproblem is some constant fraction of the original problem.

The way recursion works is by solving the smaller subproblems individually and then aggregating the results to return the final solution.

Stack Overflow

So what happens if you keep calling functions that are nested inside each other?

When this happens, it’s called a stack overflow.

And that is one of the challenges you need to overcome when it comes to recursion and recursive algorithms.

// When a function calls itself,
// it is called RECURSION
function inception() {
inception();
}
inception();
// returns Uncaught RangeError:
// Maximum call stack size exceeded

Avoiding Stack Overflow

In order to prevent stack overflow bugs, you must have a base case where the function stops making new recursive calls.

If there is no base case then the function calls will never stop and eventually a stack overflow will occur.

Here is an example of a recursive function with a base case.

The base case is when the counter becomes bigger than 3.

let counter = 0;
function inception() {
    console.log(counter)
    if (counter > 3) {
        return 'done!';
    }
    counter++
    return inception();
}

When you run this program, the output will look like this:

This program does not have a stack overflow error because once the counter is set to 4, the if statement’s condition will be True and the function will return ‘done!’, and then the rest of the calls will also return ‘done!’ in turn.

pseudocode:

function recursiveFunction(parameters):
    if base case:
        return base case result
    else:
        break problem into smaller subproblems
        recursively call function with smaller subproblems
        combine results from subproblems
        return combined result

Example 1: Factorial

// Write two functions that find the factorial of any
// number. One should use recursive, the other should just
// use a for loop

function findFactoriatIterative(num){ // O(n)
    let res = num;
    for (let i = num; i > 0; i--){
        if (i != 1){
        res = res * (i-1);
        }
    }
    // console.log(res)
    return res

}

function findFactoriatRecursive(num){ // O(n)
    if (num == 2) {
        return 2;
    }
    return num * findFactoriatRecursive(num-1)
}

findFactoriatIterative(5)

// Output: 120

---

Example 2: Fibonacci

// Given a number N return the index value of the Fibonacci
// sequence, where the sequence is:

// o, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...
// the pattern of the sequence is that each value is the sum of
// the 2 previous values, that means that for N=5 -> 2+3

function fibonacciIterative(n){
    let arr = [0,1];
    for (let i = 2; i < n +1; i++){ // O(n)
        arr.push(arr[i-2] + arr[i-1]);
    }
    console.log(arr[n])
    return arr[n]
}

// fibonacciIterative(3);

function fibonacciRecursive(n) { // O(2^n)
    if (n < 2) {
        return n;
    }
    return fibonacciRecursive(n-1) + fibonacciRecursive(n-2)
}

fibonacciRecursive(3);

// Output: 2

Recursion vs. Iteration

Recursion	Iteration
Recursion uses the selection structure.	Iteration uses the repetition structure.
Infinite recursion occurs if the step in recursion doesn't reduce the problem to a smaller problem. It also becomes infinite recursion if it doesn't convert on a specific condition. This specific condition is known as the base case.	An infinite loop occurs when the condition in the loop doesn't become False ever.
The system crashes when infinite recursion is encountered.	Iteration uses the CPU cycles again and again when an infinite loop occurs.
Recursion terminates when the base case is met.	Iteration terminates when the condition in the loop fails.
Recursion is slower than iteration since it has the overhead of maintaining and updating the stack.	Iteration is quick in comparison to recursion. It doesn't utilize the stack.
Recursion uses more memory in comparison to iteration.	Iteration uses less memory in comparison to recursion.
Recursion reduces the size of the code.	Iteration increases the size of the code.

Recursion Good at 😀:

• DRY

• Readability

Recursion Bad at 😒:

• Large Stack

When do I need to use Recursion?

Every time you are using a tree or converting Something into a tree, consider Recursion.

1 . Divided into a number of subproblems that are smaller instances of the same problem.

1. Each instance of the subproblem is identical in nature.

2. The solutions of each subproblem can be combined to solve the problem at hand.