Что я знаю о рекурсивных функциях

Проклятие любого начинающего программиста. Функция, которая вызывает сама себя? Имеет смысл, пока вы не должны написать это. Я все еще нахожусь в начале своего пути разработки, поэтому я еще не сталкивался с ситуацией, которая действительно нуждалась бы в рекурсии. Тем не менее, узнавать о них было весело, поэтому я попытаюсь резюмировать то, что я узнал, своими словами.

Когда я впервые пытался понять эту идею, у меня сложилось впечатление, что функция полностью выполнялась многократно, пока не было выполнено условие, но это не так. На самом деле каждый раз, когда функция вызывает сама себя, предыдущее выполнение приостанавливается до тех пор, пока последующий вызов функции не будет полностью выполнен. Само по себе это знание не особо помогло мне понять, что происходит под капотом, поэтому продемонстрирую на примере рекурсивной функции из freeCodeCamp. Целью countup(n) является создание массива, который считает до заданного числа n .

function countup(n) {
  if( n < 1) {
    return [];
  } else {
    const countArray = countup(n - 1);
    countArray.push(n);
    return countArray;
  }
}
// returns [1, 2, 3, 4, 5... n];

Давайте разберем это. Сначала программа проверяет, является ли n < 1 . Если это так, верните пустой массив [] . Если нет, объявите новую переменную с именем countArray и установите ее равной… этой функции? Да, но с одним отличием: переданное в него значение на единицу меньше, чем n . Вот где это становится странным, но это легче визуализировать с переданным фактическим значением.

Первый звонок:countup(3)

Сначала мы проверяем, если 3 < 1. Это не так, поэтому мы переходим к первой строке оператора else:

const countArray = countup(3 - 1);

Что мы имеем на данный момент:

countup(3){
  const countArray = countup(2);
  //...
}

Обратите внимание, что еще ничего не возвращено. Так что начальная цифра countup(3) пока стоит на паузе.

Второй звонок: countup(2)

Опять же, мы проверяем, если 2 < 1 . Игральных костей нет, поэтому читается первая строка оператора else:

const countArray = countup(2 - 1);

Что мы имеем на данный момент:

countup(3) {
  const countArray = countup(2);
                     
                     countup(2) {
                       const countArray = countup(2 - 1);

Еще ничего не вернулось. countup(3) и countup(2) просто застряли в подвешенном состоянии, пока не получат значение для присвоения countArray. Итак, как нам это сделать? Не забывайте о первом условном выражении countup. Это условие, которое мы проверяем, называется базовым случаем. Базовый вариант обязателен. Если базовый случай не указан, вы просто получите бесконечный цикл, что всегда, насколько я знаю, плохо.

nвызов:

Итак, для нашей функции countup базовым случаем является n < 1. n уменьшается на 1 перед передачей в каждый последующий вызов функции до тех пор, пока n < 1оценивается как true, после чего возвращается пустой массив []. Затем цикл начинает обратный. Этот пустой массив передается до countup(1), а countArray, наконец, присваивается значение, и остальная часть кода в функции может выполняться. Я использовал свои навыки рисования на профессиональном уровне, чтобы сделать блок-схему:

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

Заключение

Главное понимать, что рекурсивная функция — это не просто function = function = function -> . . .. Рекурсивная функция больше похожа на function{ function { function { function { base case }}}}.

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

Рекурсия может быть очень полезна при обработке данных. Двоичное дерево поиска (BST) распространено в запросах к базе данных, и рекурсия может искать все BST с помощью всего нескольких строк кода, независимо от размера дерева. Таким образом, рекурсия может быть головной болью, но может пригодиться в любом виде разработки.