Разбейте это на базовый вариант!

Функция, которая вызывает сама себя, которая вызывает себя, которая вызывает себя ... Рекурсия может быть сложной задачей, чтобы понять ваш мозг! 😵

Будь проще

Многие люди выбирают сложную задачу в качестве первой попытки рекурсии. Часто проблема связана с продвинутыми структурами данных, такими как деревья. Во многих смыслах это имеет смысл! Это типы проблем, которые можно упростить с помощью рекурсии. Рекурсия лучше всего подходит для решения проблем, когда вы можете разделить ее на более мелкие задачи.

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

Сломай

Если вы можете справиться с циклами кодирования, вы сможете научиться рекурсии!

Возьмите цикл while:

while(condition) { /* body */ }

В этом цикле мы выполняем блок тела, пока выполняется условие.

Вместо условия продолжения работы рекурсивные алгоритмы достигают точки остановки и возврата. Этот момент обычно называют базовым случаем.

Возьмем пример. Представьте, что мы считаем квадраты. Начните сверху со счета ноль и считайте по одному квадрату за раз:

Представьте каждый прямоугольник выше как вызов функции. Мы выполняем Body с новыми аргументами, пока не дойдем до нашего базового случая. В этот момент мы возвращаем наш окончательный счет, 3.

  • Body: Удалите квадрат, увеличьте количество.
  • Аргументы: квадраты и счет.
  • Базовый вариант: квадратов не осталось.

Когда вы пишете рекурсивное решение, помните о двух вещах:

  1. Каждый раз, когда вы вызываете функцию, аргумент должен изменяться. В частности, один аргумент должен быть изменен на базовый вариант.
  2. Определите базовый вариант. Выясните, когда закончится рекурсия! Если у вас нет места для остановки, вы получите переполнение стека вызовов.

Пример кода

Давайте подумаем о другой простой задаче, которая обычно решается итеративно: суммировании массива чисел.

const numbers = [1,2,3];

Итеративное решение этой проблемы несложно!

function total(numbers) {
  let sum = 0;
  for(let i = 0; i < numbers; length; i++) {
    sum += numbers[i];
  }
  
  return sum;
}

Что, если бы мы хотели решить эту проблему рекурсивно?

Начнем с чисел [1,2,3] и суммы 0.

Хорошим первым шагом было бы заранее продумать наш базовый вариант. Как узнать, когда остановиться? Одно из решений - удалять элемент из массива каждый раз при рекурсии. Таким образом, когда массив пуст, мы знаем, что пора остановиться и вернуть сумму.

Каждый раз, когда мы удаляем элемент, мы можем добавить его к сумме, поэтому мы накапливаем сумму к концу рекурсии!

Как бы это выглядело как функция JavaScript?

function total(numbers, sum = 0) {
  // base case
  if(numbers.length === 0) return sum;
  
  // remove an element, add it to sum 
  sum += numbers.pop();
  
  // recurse 
  return total(numbers, sum);
}

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

total([1,2,3], 0);
 total([1,2], 1);
  total([1], 2);
   total([], 3);

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

Помните, что pop изменяет исходный массив! Это может повлиять на любую часть программы, содержащую ссылку на массив.

Это не единственное решение проблемы рекурсивно. Другое решение - сохранить индекс. На самом деле это работает очень похоже на цикл:

function total(numbers, index = 0, sum = 0) {
  if(numbers.length === index) return sum;
  sum += numbers[index];
  return total(numbers, index + 1, sum);
}

В этом случае мы не меняем номера нашего массива. Вместо этого мы увеличиваем индекс. Мы используем этот индекс для чтения чисел из массива и сложения их суммы. Как только индекс достигает длины массива, мы полностью возвращаем сумму вверх по стеку вызовов.

total([1,2,3], 0, 0);
 total([1,2,3], 1, 1);
  total([1,2,3], 2, 3);
   total([1,2,3], 3, 6);

Увидеть разницу? Мы не изменяем массив каждый раз. Вместо этого мы изменяем индекс. Как и условие цикла, ваш базовый случай может быть любым по вашему выбору!

Наконец, я предлагаю еще одно решение:

function total(numbers) {
  if(numbers.length === 0) return 0;
  
  return numbers.pop() + total(numbers);
}

Это решение немного сложнее. Вместо того, чтобы накапливать сумму и передавать ее вниз по стеку вызовов, мы добавляем число к возвращаемому значению каждого рекурсивного вызова. Аккуратно, а?

Готовы к испытаниям кода рекурсии?

Попробуйте это Учебное пособие, не выходя из собственного веб-браузера! 💻

Следуйте за нами в Twitter 🐦 или присоединяйтесь к нам в ChainShot, чтобы пройти путь от нулевого опыта программирования до разработчика блокчейнов!