📖 JavaScript Recursion

Recursion is a powerful programming technique where a function calls itself to solve a problem. It is particularly useful for problems that can be divided into smaller, similar subproblems. Understanding recursion can help you write cleaner and more efficient code for complex tasks.

Task

Learn how to use recursion to solve problems that involve repeated subproblems. Recursion can simplify the code for tasks such as directory traversal and flattening nested arrays.

Coding Examples

Directory Traversal

One practical example of recursion is traversing a directory structure. This example shows how to recursively traverse an object representing a directory tree.


// Recursive directory traversal
const directory = {
    name: 'root',
    files: [
        { name: 'file1.txt' },
        { name: 'file2.txt' },
        {
            name: 'subdir',
            files: [
                { name: 'file3.txt' },
                { name: 'file4.txt' }
            ]
        }
    ]
};

function listFiles(dir) {
    let files = [];
    dir.files.forEach(file => {
        if (file.files) {
            files = files.concat(listFiles(file)); // Recursive call
        } else {
            files.push(file.name);
        }
    });
    return files;
}

console.log(listFiles(directory)); // Output: ['file1.txt', 'file2.txt', 'file3.txt', 'file4.txt']

Here's how it works:

  1. const directory = {...} - Defines an object representing a directory tree.
  2. function listFiles(dir) { - Defines a function listFiles that takes a directory object dir as an argument.
  3. let files = []; - Initializes an empty array to hold the file names.
  4. dir.files.forEach(file => { ... }); - Iterates over each file in the directory.
  5. if (file.files) { files = files.concat(listFiles(file)); } - If the file is a directory, recursively call listFiles and concatenate the result.
  6. else { files.push(file.name); } - If the file is not a directory, add its name to the files array.
  7. return files; - Returns the array of file names.
  8. console.log(listFiles(directory)); // Output: ['file1.txt', 'file2.txt', 'file3.txt', 'file4.txt'] - Calls the listFiles function with the directory object, resulting in a list of all file names.

Flattening Nested Arrays

Another example of recursion is flattening a nested array. This example shows how to recursively flatten an array of nested arrays.


// Recursive array flattening
const nestedArray = [1, [2, [3, [4, 5]]], 6];

function flattenArray(arr) {
    let flatArray = [];
    arr.forEach(element => {
        if (Array.isArray(element)) {
            flatArray = flatArray.concat(flattenArray(element)); // Recursive call
        } else {
            flatArray.push(element);
        }
    });
    return flatArray;
}

console.log(flattenArray(nestedArray)); // Output: [1, 2, 3, 4, 5, 6]

Here's how it works:

  1. const nestedArray = [...]; - Defines a nested array.
  2. function flattenArray(arr) { - Defines a function flattenArray that takes an array arr as an argument.
  3. let flatArray = []; - Initializes an empty array to hold the flattened elements.
  4. arr.forEach(element => { ... }); - Iterates over each element in the array.
  5. if (Array.isArray(element)) { flatArray = flatArray.concat(flattenArray(element)); } - If the element is an array, recursively call flattenArray and concatenate the result.
  6. else { flatArray.push(element); } - If the element is not an array, add it to the flatArray.
  7. return flatArray; - Returns the flattened array.
  8. console.log(flattenArray(nestedArray)); // Output: [1, 2, 3, 4, 5, 6] - Calls the flattenArray function with the nested array, resulting in a flattened array.

Putting It Into Action

Create an HTML file and include the following script to see recursion in action. This script will demonstrate how to use recursion for directory traversal and flattening nested arrays.


<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Recursion Example</title>
</head>
<body>
    <script>
        // Recursive directory traversal
        const directory = {
            name: 'root',
            files: [
                { name: 'file1.txt' },
                { name: 'file2.txt' },
                {
                    name: 'subdir',
                    files: [
                        { name: 'file3.txt' },
                        { name: 'file4.txt' }
                    ]
                }
            ]
        };

        function listFiles(dir) {
            let files = [];
            dir.files.forEach(file => {
                if (file.files) {
                    files = files.concat(listFiles(file)); // Recursive call
                } else {
                    files.push(file.name);
                }
            });
            return files;
        }

        console.log(listFiles(directory)); // Output: ['file1.txt', 'file2.txt', 'file3.txt', 'file4.txt']

        // Recursive array flattening
        const nestedArray = [1, [2, [3, [4, 5]]], 6];

        function flattenArray(arr) {
            let flatArray = [];
            arr.forEach(element => {
                if (Array.isArray(element)) {
                    flatArray = flatArray.concat(flattenArray(element)); // Recursive call
                } else {
                    flatArray.push(element);
                }
            });
            return flatArray;
        }

        console.log(flattenArray(nestedArray)); // Output: [1, 2, 3, 4, 5, 6]
    </script>
</body>
</html>

Challenge

Create a recursive function to calculate the depth of a nested array. The depth of an array is the maximum number of nested arrays within it.

In order to check your learning, you should attempt to create a solution before revealing the provided solution below.


// Recursive depth calculation
function calculateDepth(arr) {
    if (!Array.isArray(arr)) {
        return 0; // Base case: if it's not an array, depth is 0
    }
    return 1 + Math.max(0, ...arr.map(calculateDepth)); // Recursive case
}

console.log(calculateDepth([1, [2, [3, [4, 5]]], 6])); // Output: 4

References