Статьи

Что такое рекурсия?



Рекурсия - это приём, который часто используется в программировании.
Чтобы рассмотреть что такое рекурсия давайте разберем, что такое функция. Функция в программировании - это именованный участок кода, который выполняет определённую задачу, функцию.

Например, ниже функция, которая называется pow и выполняет возведение в степень. Она принимает на вход 2 значения - число, которое возводить и степень, в которую возводить. Как мы знаем возведение в степень - это умножение числа на само себя указанное в степени количество раз. То есть 2 в степени 2 = 2*2. 2 в степени 5=2*2*2*2*2
————
function pow(x, n) { // функция с параметрами
let result = 1;
for (let i = 0; i < n; i++) { //цикл с условиями
result = result * x;
}
return result;
}
————
Чтобы выполнить функция её нужно вызвать следующим образом
————
pow(2,2);
————

Действие, которое выполняется в цикле этой функции довольно однотипное, и следовательно функцию можно сделать рекурсивной. Рекурсивная функция - это когда функция вызывает саму себя. То есть на каждый новый вызов будет происходить умножение.
Пример:
————
function pow(x, n) {
if (n == 1) {
return x;
} else {
return x * pow(x, n - 1);
}
}
————
Здесь мы избавились от цикла. И каждый новый запуск происходит с уменьшением степени до тех пор, пока степень не станет 1. Эта 1 указывает нам на то, что пора рекурсию завершить. Если это условие не указать, то она будет выполняться бесконечно.

То есть, рекурсия - это вызов функции самой себя.

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

Больше информации можно прочитать вот тут https://learn.javascript.ru/recursion