DEV Community

Cover image for What is a JavaScript Recursive Function? πŸ”
Anton
Anton

Posted on • Updated on

What is a JavaScript Recursive Function? πŸ”

Recursion is a mathematical concept that has many applications in daily life.

As website developers, we encounter recursive functions every day.

This tutorial will explore the pattern of problems, which can be solved using recursion.

Β 

Basic Concept


function recurse() {
    // 2nd call to itself
    recurse();
}

// 1st call
recurse();
Enter fullscreen mode Exit fullscreen mode

Each recursive function must have a base case (also called termination condition), where it stops the recursion, or else it will continue calling itself indefinitely.

function recurse() {
    if (terminate)
        return; // stop calling recurse();

    // continue recurse() if there is no termination
    recurse();
}

recurse();
Enter fullscreen mode Exit fullscreen mode

Β 

While Loop and Recursion Comparison


The recursion technique looks similar to the while loop.

Imagine that you need to multiply the desired number by themselves X times.

For example: 2 * 2 * 2 = 8

Β 

While Loop

function multiply(n, x) {
    let i = 0;
    let res = 1;
    while (i < x) {
      res = res * n;
      i++;
    }
    return res;
}
Enter fullscreen mode Exit fullscreen mode

How does the loop works?

multiply(2,3)

1. i = 0, res = (1) * 2       // 0 < 3 continue ...
2. i = 1; res = (2) * 2       // 1 < 3 continue ...
3. i = 2; res = (2 * 2) * 2   // 2 < 3 continue ...
4. i = 3; res = (2 * 2 * 2)   // 3 < 3 (false) break and return 8
Enter fullscreen mode Exit fullscreen mode

Β 

Recursion πŸ”

function multiply(n, x) {
    return x > 1 ? n * multiply(n, x - 1) : n;
}
Enter fullscreen mode Exit fullscreen mode

How does the recursion works?

recursion.jpg

Β 

Examples


#1 (String URL Encode)

Let's imagine we need to URL encode the string <html> 5 times

The output should look like this:
%252525253Chtml%252525253E

Loop Solution

function encode(str, n) {
    let i = 0;
    while (i < n) {
      str = encodeURI(str)
      i++;
    }
    return str;
}
Enter fullscreen mode Exit fullscreen mode

Recursion Solution πŸ”

function encode(str, n) {
    return n ? encode(encodeURI(str), n - 1) : str;
}
Enter fullscreen mode Exit fullscreen mode

Β 

#2 (String URL Decode)

Let's imagine we need to decode an URL that has been encoded multiple times

For example let's take previous URL encoded string:
%252525253Chtml%252525253E

The output result will be: <html>

Loop Solution

function decode(str) {
    while (str !== decodeURI(str)) {
      str = decodeURI(str)
    }
    return str;
}
Enter fullscreen mode Exit fullscreen mode

Recursion Solution πŸ”

function decode(str) {
    return str !== decodeURI(str) ? decode(decodeURI(str)) : str;
}
Enter fullscreen mode Exit fullscreen mode

Β 

#3 (String Replace)

Imagine you need to replace bad tags, like <script>, from your HTML code

1st case: hello<script> world<script>

2nd case: hello<sc<script>ript>world

With the first case, we can easily do something like this:

let html_code = 'hello<script> world<script>';
let output = html_code.replaceAll('<script>','');
// output: hello world
Enter fullscreen mode Exit fullscreen mode

But.. with the second case it will fail:

let html_code = 'hello<sc<script>ript> world';
let output = html_code.replaceAll('<script>','');
// output: hello<script> world
Enter fullscreen mode Exit fullscreen mode

Here is where Recursion comes to the rescue

Recursion Solution πŸ”

function clean_html(html, bad_tag) {
    let c_html = html.replaceAll(bad_tag, '');
    return html === c_html ? html : clean_html(c_html, bad_tag)
}

clean_html('hello<sc<script>ript> world', '<script>');

// output: hello world
Enter fullscreen mode Exit fullscreen mode

Β 

#4 (Find Nested Elements)

In this example, we need to find category by ID in a deeply nested array

Our target is a category with ID number 5

let the_category_list = [
    {"id" : 1, "name" : "fruits", "child_list" : [
        {"id" : 2, "name" : "apple", "child_list" : [
            {"id" : 4, "name" : "red apple", "child_list" : []},
            {"id" : 5, "name" : "green apple", "child_list" : []}
        ]},
        {"id" : 3, "name" : "banana", "child_list" : []}
    ]}
]
Enter fullscreen mode Exit fullscreen mode

Recursion Solution πŸ”

function find_cat_by_id(id, category_list) {
    let found_category = false;

    category_list.forEach(cat => {
        if (cat.id === id)
            found_category = cat ;

        if (found_category === false && cat.child_list.length)
            found_category = find_cat_by_id(id, cat.child_list)
    }); 

    return (found_category) ? found_category : false;
}

find_cat_by_id(5, the_category_list)

// Output: {id: 5, name: "green apple", child_list: Array(0)}
Enter fullscreen mode Exit fullscreen mode

Β 

#5 (Factorial Using Recursion)

This example will show you how to write a factorial program in javascript using recursion

Let’s imagine we need a factorial of 5: 1 * 2 * 3 * 4 * 5 = 120

Recursion Solution πŸ”

function factorial(x) {
    return x ? x * factorial(x - 1) : 1; 
}
Enter fullscreen mode Exit fullscreen mode

Β 

#6 (Fibonacci Series Using Recursion)

In this example, you will learn how to write a program to print the Fibonacci series using recursion

Fibonacci sequence is written as: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Recursion Solution πŸ”

function fibonacci(num) {
    return num < 2 ? num : fibonacci(num - 1) + fibonacci(num - 2);
}

function fibonacci_printer(numberOfTerms) {
    let out = [];    for(let i = 0; i < numberOfTerms; i++) {
        out.push(fibonacci(i));
    }    console.log(out.join(', '));
}
Enter fullscreen mode Exit fullscreen mode

To use this program, you need to call fibonacci_printer(5) and the output will be: 0, 1, 1, 2, 3

Thanks for reading!

More examples will be added later.

Follow me on Twitter - https://twitter.com/therceman

Top comments (2)

Collapse
 
marzelin profile image
Marc Ziel

Plot twist: recursion is just a loop in disguise.

Any recursive function can be represented as a loop and vice versa.

Collapse
 
therceman profile image
Anton

Yes :) I couldn't find an example where the desired task can be completed only using recursion and nothing else