JavaScript in Detail: From Beginner to Advanced/

...

/

Recursion

Recursion

Introduction to recursion and how to think recursively in JavaScript.

We'll cover the following...

Background

We can now introduce any number and types of functions to morph our input to a certain output with function composition. Despite composing functions with multiple occurrences of the same function in the list, we haven’t tried calling the function within itself. Calling the same function within its body allows us to enter a new realm of programming called recursive programming.

Introduction to recursion

Recursion is when a function calls itself again and again until it reaches a specified stopping condition. This is called a recursive function. The recursive functions can be the following types:

  • Direct recursion happens when a function calls itself directly in its body or definition.
  • Indirect recursion is when two or more functions call themselves indirectly from each other.

Composition of recursive function

A recursive function consists of these cases.

  • Base case: Condition where the function exits.
  • Recursive case: Condition where it recurses (calls itself again).

In either case, the function is responsible for solving a partial problem, in the base case, before or after recursing.

Before continuing, let’s focus on solving the partial problem by identifying the sub-problem.

Designing and solving sub-problems

Whenever we come across recursion, the main idea involves solving a sub-problem. The size of the sub-problem is up to you. Take a look at the following example.

Press + to interact
function power(base, power)
{
    if(power === 0){
        // Basecase # 1
        // directly solve the problem
        return 1;
    }
    else if(power === 1){
        // Basecase # 2
        // directly solve the problem
        return base;
    }
    else{
        // Recursive case
        // solve sub-problem
        // sub problem is multiplying it to the base one less value of power
        var sub_solution = power_helper(base, power -1);
        var solution =  sub_solution * base;
        return solution;
    }
}

The above example is a solved solution where we calculate the exponent power of the number base. Since the idea is to solve only a sub-problem, only solve the ...