Работа с рекурсией в JavaScript

В программировании есть такое понятие, как рекурсия - это когда функция вызывает сама себя.

Давайте посмотрим на примере.

Выведем с помощью рекурсии числа от 1 до 10:

let i = 1; function func(){ console.log(i); i++; if (i <= 10){ func(); // здесь функция вызывает сама себя } } func();

Давайте обсудим, как работает этот код.

У нас есть глобальная переменная i и функция func, внутри которой в консоль выводится содержимое переменной i, а затем делается ++.

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

Получится, что функция будет вызывать сама себя до тех пор, пока i не станет больше 10.

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

Пример с параметром

Давайте, с помощью рекурсии последовательно выведем элементы массива. Пусть массив изначально передается параметрам функции:

func([1, 2, 3]);

Давайте пока без рекурсии используя метод shift выведем все элементы массива по очереди:

function func(arr) { console.log(arr.shift()); // выведет 1 console.log(arr); // выведет [2, 3] - массив уменьшился console.log(arr.shift()); // выведет 2 console.log(arr); // выведет [3] - массив уменьшился console.log(arr.shift()); // выведет 3 console.log(arr); // выведет [] - массив пуст } func([1, 2, 3]);

Как вы видите, метод shift вырезает и возвращает первый элемент массива, при этом сам массив уменьшается на этот элемент.

Давайте теперь используем рекурсию:

function func(arr) { console.log(arr.shift(), arr); if (arr.length != 0) { func(arr); } } func([1, 2, 3]);

На самом деле, конечно же, проще всего перебрать элементы массива циклом. Приведенные примеры пока просто демонстрируют работу рекурсии на простых примерах (не жизненных). Более полезные примеры применения рекурсии просто более сложные, мы их разберем чуть ниже.

Сумма элементов массива

Давайте теперь не будем выводить элементы массива на экран, а найдем сумму элементов этого массива.

Приведу сразу код, выполняющий описанное (далее будет подробный разбор):

function getSum(arr) { let sum = arr.shift(); if (arr.length != 0) { sum += getSum(arr); } return sum; } console.log(getSum([1, 2, 3]));

Давайте пошагово разберемся с тем, что происходит в этом коде.

Итак, вот расписан первый вызов функции:

function getSum(arr) { // здесь массив arr = [1, 2, 3] let sum = arr.shift(); // в sum запишется первый элемент массива, то есть 1 // здесь массив arr = [2, 3] // длина массива больше нуля, значит попадем в иф if (arr.length != 0) { // здесь в sum лежит число 1 sum += getSum(arr); // параметром рекурсии передается массив [2, 3] //!! далее код не выполняется, так как //!! мы опять попадаем в функцию getSum на следующий шаг рекурсии //!! смотрите пример кода ниже } // сюда мы пока не попадаем, так как ушли в рекурсию return sum; } console.log(getSum([1, 2, 3]));

Вот мы первый раз попадаем в рекурсию, то есть функция getSum первый раз вызывается внутри себя:

function getSum(arr) { // здесь массив arr = [2, 3] let sum = arr.shift(); // в sum запишется первый элемент массива, то есть 2 // здесь массив arr = [3] // длина массива больше нуля, значит попадем в иф if (arr.length != 0) { // здесь в sum лежит число 2 sum += getSum(arr); // параметром рекурсии передается массив [3] //!! далее код не выполняется, так как //!! мы опять попадаем в функцию getSum на следующий шаг рекурсии //!! смотрите пример кода ниже } // сюда мы пока не попадаем, так как ушли в рекурсию return sum; } console.log(getSum([1, 2, 3]));

Вот мы второй раз попадаем в рекурсию, то есть функция getSum второй раз вызывается внутри себя:

function getSum(arr) { // здесь массив arr = [3] let sum = arr.shift(); // в sum запишется первый элемент массива, то есть 3 // здесь массив arr = [] // длина массива равна нулю, значит не попадем в иф if (arr.length != 0) { // сюда мы уже не попадаем sum += getSum(arr); } //!! возвращаем в родительский вызов содержимое sum, то есть число 3: return sum; } console.log(getSum([1, 2, 3]));

Как вы видите, это последний вызов функции внутри себя, так как в этом вызове массив закончился.

Именно сейчас срабатывает первый return и выполнение кода перескакивает обратно на первый шаг рекурсии и продолжается с 13 строки:

function getSum(arr) { // здесь массив arr = [2, 3] let sum = arr.shift(); // в sum запишется первый элемент массива, то есть 2 // здесь массив arr = [3] // длина массива больше нуля, значит попадем в иф if (arr.length != 0) { // здесь в sum лежит число 2 //!! ВЫПОЛНЕНИЕ ПРОДОЛЖАЕТСЯ ОТСЮДА sum += getSum(arr); //!! функция вернула 3, в sum лежит 2, итого в sum запишется 5 } //!! возвращаем в родительский вызов содержимое sum, то есть число 5: return sum; } console.log(getSum([1, 2, 3]));

Теперь выполнение кода перескакивает обратно на первый шаг рекурсии и продолжается с 13 строки:

function getSum(arr) { // здесь массив arr = [1, 2, 3] let sum = arr.shift(); // в sum запишется первый элемент массива, то есть 1 // здесь массив arr = [2, 3] // длина массива больше нуля, значит попадем в иф if (arr.length != 0) { // здесь в sum лежит число 1 //!! ВЫПОЛНЕНИЕ ПРОДОЛЖАЕТСЯ ОТСЮДА sum += getSum(arr); //!! функция вернула 5, в sum лежит 1, итого в sum запишется 6 } //!! возвращаем во внешний мир содержимое sum, то есть число 6: return sum; } //!! вот здесь выведется результат последнего return: console.log(getSum([1, 2, 3])); // выведет 6

Сделайте функцию, которая с помощью рекурсии выведет первые 10 чисел Фибоначчи. Числа Фибоначчи строятся следующим образом: каждое новое число равно сумме двух предыдущих. Первые два числа Фибоначчи - это 1 и 2. Следующее число будет равно 1 + 2 = 3, следующее число будет равно 2 + 3 = 5 и так далее.

Вот основа кода, который вы должны написать:

function func(prevPrevNum, prevNum){ // тут код с рекурсией, который вы должны написать } func(1, 2); // вызываем функцию с первыми двумя числами

Модифицируйте предыдущую задачу так, чтобы функция не выводила числа, а возвращала массив первых 10 чисел Фибоначчи:

console.log(func(1, 2)); // выведет массив чисел

Редуцирование числа

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

Посмотрим, что имеется ввиду. Давайте сложим цифры нашего числа 12345: 1 + 2 + 3 + 4 + 5 = 15. Как вы видите, мы получили число 15. Давайте опять сложим его цифры: 1 + 5 = 6. На этом остановимся, так как число стало однозначным.

Когда такое может пригодится? К примеру, есть признак деления на числа на 9: если сумма цифр числа делится на 9, то и число делится на 9.

Давайте проверим делится ли какое-нибудь число на 9. Возьмем для примера число 2187. Сложим его цифры, получим 18. Так как результат - двухзначное число, опять сложим полученные цифры - получим 9. Очевидно, что число 9 делится на 9, значит и число 2187 делится на 9.

Решим поставленную задачу.

Для начала давайте сделаем функцию getDigitsSum, которая параметром будет получать число и возвращать сумму цифр этого числа:

function getDigitsSum(num) { return getSum(getDigits(num)); } function getSum(arr) { let sum = 0; for (let elem of arr) { sum += Number(elem); } return sum; } function getDigits(num) { return String(num).split(''); }

Используя функцию getDigitsSum напишем теперь функцию reduceNum, решающую нашу изначальную задачу:

function reduceNum(num) { let sum = getDigitsSum(num); if (sum <= 9) { return sum; } else { return reduceNum(sum); } } console.log(reduceNum(2187)); // выведет 9

Давайте разберемся, как это работает. Функция reduceNum вызывает функцию getDigitsSum, передавая в него число, а назад получая сумму цифр.

Далее с помощью if мы определяем полученная сумма меньше 9 или нет. Если меньше - то возвращаем полученное число, а если больше - передаем полученную сумму в качестве параметра функции reduceNum, то есть сами себе.

Таким образом у нас будут последовательные рекурсивные вызовы функции reduceNum до тех пор, пока сумма цифр не станет однозначным числом.

Самостоятельно, не подсматривая в код, решите описанную задачу.