Рекурсия в JavaScript

Содержание

Рекурсия в общем смысле - это повторение какого-либо объекта или процесса внутри самого этого объекта или процесса.

В программировании в том числе и в JavaScript под рекурсией чащего всего понимают метод, который предполагает создание функции, которая вызывает саму себя до тех пор пока программа не достигнет необходимого результата.

Рассмотрим простой пример

    
    let days = 0;
    function howMuchToLearnJS() {
        days++;
        console.log(days);
        howMuchToLearnJS();
    }
        howMuchToLearnJS();

В данном примере мы написали функцию, которая:

В результате мы получим рекурсию и в дополнение «бесконечный» вывод чисел, каждое из которых будет больше на 1-цу предыдущего. Однако есть такое понятие, как стек, который рассчитан на ограниченное количество вложенных вызовов. В итоге, где-то на 11 тысячах вывод прекратиться и console выдаст ошибку Uncaught RangeError: Maximum call stack size exceeded - превышен максимальный размер стека вызовов.

ошибка переполнение стека

Для того, чтобы такой ситуации не произошло в рекурсивной функции прописывают базовый случай - условие, когда выполнение программы должно закончится. Для большей надежности рекомендуют сначала прописать условие выхода, а затем описывать функционал.

    
    let days = 0;
    function howMuchToLearnJS() {
        if (days === 400) return; // условие выхода
        days++;
        console.log(days);
        howMuchToLearnJS();
    }
    howMuchToLearnJS();

Цикл и рекурсия

Любая задача, которую можно решить рекурсией, также решается и с помощью цикла. Перепишим наш пример.

    
    for (let days = 0; days <= 400; days++) {
        console.log(days);
    }

Тут возникает вопрос, зачем использовать рекурсию, когда можно обойтись циклом. Дело в том, что в разных ситуациях один метод можно применять с большей эффективностью, чем другой и наоборот.

Плюсы рекурсии

Плюсы цикла

Точного ответа, что лучше цикл и рекурсия нет. Все зависит от конкретной задачи.

Контекст выполнения и стек

Контекст выполнения - это структура данных, содержащая информацию о вызываемой функции. Другими словами, когда функция запускается, создается контекст, в который записывается все относящееся к вызываемой программе от переменных до того места где находился интерпретатор, когда она была вызвана.

Стек в случае с рекурсией - это специальная структура данных в которую записывается по порядку информация о каждом вызове функции самой себя, в том числе и первом вызове.

Отсюда исходит основная опасность работы с рекурсией - это переполнение стека. Глубина рекурсии равняется количеству контекстов, которые хранятся в стеке одновременно, а это число ограничено мощностью компьютера - обычно от 10 000 до 12 000. Для недопущения переполнения и существует базовый случай, тоесть условие, когда вызов функции самой себя должен прекратиться.

Факториал

Разбавим теорию популярным примером и напишим функцию вычисляющую факториал.

Факториал - это произведение всех натуральных чисел от 1 до заданного включительно.

Способ №1 - рекурсия

    
    let s = 1;  
    function calcFactorial(n) {
        if (n === 0) return;
        s = s * n;
        calcFactorial(n - 1);
    }
    calcFactorial(10);
    console.log(s);

Способ №2 - рекурсия

    
    function calcFactorial(n) {
        if (n <= 1) {
            return 1;
        }
        return n * calcFactorial(n - 1);
    }
    console.log(calcFactorial(10));

Способ №3 - цикл

    
    function calcFactorial(n) {
        let s = 1;
        for (let i = 1; i <= n; i++) {
            s = s * i;
        }
        console.log(s);
    }
    calcFactorial(10);

Сложные структуры и рекурсия

Объекты с неизвестной глубиной вложенности - это классический пример, когда с помощью рекурсии задачу решить намного легче, чем с помощью цикла.

    
    let jsUniversity = {
        javascript: [{
            name: 'Дмитрий',
            payment: 20000,
        }, {
            name: 'Ольга',
            payment: 20000
        }, {
            name: 'Вероника',
            payment: 20000
        }],
        
        react: {
            'full time': [{
            name: 'Татьяна',
            payment: 30000,
            }, {
            name: 'Витор',
            payment: 30000,
            }],
        
            extramural: [{
            name: 'Павел',
            payment: 25000,
            }, {
            name: 'Денис',
            payment: 25000,
            }]
        }
    };
            
            
    function income(devUniversity) {
    if (Array.isArray(devUniversity)) {
        return devUniversity.reduce((prev, current) => prev + current.payment, 0);
    } else {
        let sum = 0;
        for (let extramural of Object.values(devUniversity)) {
            sum += income(extramural);
        }
        return sum;
      }
    }
    
    alert(income(jsUniversity));

На входе объект с несколькими уровнями вложенности - стоит задача рассчитать доход университета со всех учеников. Если глубина структуры заранее известна, найти нужные элементы с помощью цикла не так уж и сложно, но как только появится дополнительная глубина, программу придется дописывать. В нашем случае доход рассчитан с помощью рекурсии, при добавлении новых направлений или групп, код продолжил работать корректно.

Итого

Рекурсия - это метод написания функции, когда она вызывает саму себя. С помощью рекурсии можно решить много задач, но большинство из них можно легко переписать используя цикл.

Структуры данных с глубокой вложенностью или неизвестной глубиной - отличный пример, когда рекурсия справляется с обходом лучше, чем цикл.

Базовый случай - это условие, когда рекурсия должна закончится. Такое условие важно предусмотреть, так как количество вызовов функции самой себя ограничено из-за переполнения стека.