Recursions

Recursions and Recursive functions.

Okay, I have realized that this word and concept tends to through beginners off. Assuming you understand some basic coding and know what functions/ methods/ subroutines are.

Recursion

dictionary and academic definition:

noun [mass noun] Mathematics & Linguistics
The repeated application of a recursive procedure or definition.

My way of thinking of Recursion :

A way of solving a big problem that is made up of the same small portions. We solve this kind of complex problem by breaking it into small parts of itself, then repetitively applying the same solution to each portion until we have solved the whole problem.

Recursive functions are very useful at breaking down and repeating the same steps until you reach the answer. When creating a recursive function the function should contain the logic that will be repeated as you work towards the solution and it should also contain a condition that will tell it to stop repeating itself.

Here is a good example, imagine you were tasked with adding up the sum of 11 until 275 :

0 + 11 + 22 + 33 + 44 + ... + 275

Looking at the problem closely, We need to keep on adding 11 to the result of the previous addition as we work our way towards 275 :
0 + 11 = 11
11 + 11 = 22
22 + 11 = 33
33 + 11 = 44
44 + 11 = 55

In code, this can be solved in many ways :

1. The most crude of them all is you can simply hardcode 11 + 22 ... until you reach 275 and call it a day But this will be highly inefficient :

// Worst solution 
var answer = 11 + 22 + 33 + 44 + 55 + 66 + 77 + 88 + 99 + 110 + 121 + 132 + 143 + 154 + 165 + 176 + 187 + 198 + 209 + 220 + 231 + 242 + 253 + 264 + 275;
console.log(answer);
// result : 3575

There are many reasons why this is a bad idea:
i. You will waste a lot of time writing this
ii. Two it will be very hard to maintain - imagine after all your hard work, the requirements changed instead of terminating at 275 now you have to add up to 825 or allow users to add any number that leaves no remainder when divided by 11.

Iterative approach

1. The second way of solving this which I am not completely against and most people will use is the Iterative approach (using a loop to repeat the sum-up logic until you reach a terminating state which in this case is 275. This in code will look something like this.

function sumUp(max) {
    let answer = 0
    for (i = 0; i <= max; i += 11) {
        answer += i
    }
    return answer
}
console.log(sumUp(275))
// result : 3575

Recursive approach

1. The iterative approach is not completely bad it works. But then again we can write the same thing with less code using recursions.

function SumUp(max) {
    // Base case
    if (max == 0) return 0;

    // Logic in its simplest form
    return max + SumUp(max - 11); 
}
console.log(SumUp(275));
// result : 3575

Oh, I said we can rewrite it with less code right? Let's change the function into an arrow function and then use a ternary operator in the code

const SumUp = (max) => max == 0 ? 0 :  max + SumUp(max - 11);

We now have the same logic in a single line of code, although the single line benefit will not always be the case, using recursion in certain problems makes it a lot easier to solve them.

(For Geeks) How recursions work in computers is quite interesting we have a data structure called the call stack, it is just a stack that stores information about the active subroutines of a computer program and it is also known as the execution stack, When a recursive function is called the function repetitively unpacks itself into the call stack until it reaches the base case which means the output result is not calculated immediately or before all the unpacking is done Once it's done, the functions are executed from the last pushed in function down to the first (Remember stacks follow LIFO Last In First out).

In our sum up example above the evaluation or result from the execution of the last function to go in the call stack is passed back into the next function in the call stack until all the functions are executed.

Take note (!important)

If we don't specify a base case in our recursive function the function will infinitely call itself (stack up in the call stack) and that is a BIG problem because our computers only have finite memory, The computer will eventually run out of memory. It's very important to remember to add a terminating condition when dealing with recursive functions.

The best way to think of a recursive function is it is made up of two parts:

1. The logic that solves the problem in its simplest form (Repeated logic).

2. The Base Case (a terminating condition that will stop the recursive function from calling itself).

Before I finish this article I want to give you two more examples of where you might use recursions

Example 1: Calculating a factorial of a number:
Give a number e.g 5. The factorial of 5 will be the result of 5 x 4 x 3 x 2 x 1. This can be written using recursions :

function factorial(number){
        // Base case
    if(number == 1){
      return number;
    }

        // Repeated steps
    Return number * factorial(number-1); 
}

1. The second example is when you are working with Binary Trees, it's much easier to traverse with recursions.

E.g Let's say we are tasked with implementing a function that will print out all the values it would look like this:

//.... rest of the code
    print() {
        const printRecursively = (node) => {
            // Base case
            if (node == null) {
                return;
            }
           // Repeated Steps
            printRecursively(node.left);
            console.log(node.value);
            printRecursively(node.right);
        }
        printRecursively(this.root);
    }

That's it from me I hope you enjoy this read as I enjoyed writing it cheers.