Одна из программных конструкций, с которой я всегда борюсь, — это рекурсия. Концепция рекурсии на самом деле довольно проста, но я нахожу ее неинтуитивной и сложной. Часто я слышу, как люди говорят, можно ли реализовать что-то итеративно. Но зачем кому-то хотеть писать решение рекурсивно, когда вы можете написать его итеративно? Это потому, что рекурсивное решение часто обеспечивает гораздо более чистое и элегантное решение.

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

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

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

Я думаю о рекурсии как о поездке на лифте. Вы должны подниматься и спускаться на лифте, чтобы вернуться туда, откуда пришли. Поскольку функция многократно вызывает себя в рекурсии, она добавляется в стек, как будто поднимается на лифте. Затем он попадает в базовый случай, подобно тому, как лифт попадает на верхний этаж. У него нет другого выбора, кроме как вернуться вниз. Значение, возвращаемое из базового случая, возвращается вниз, когда функции выталкиваются из стека вызовов. К тому времени, когда функция возвращается к исходной функции, она находится в результатах.

Основы рекурсии

  1. Настройка базового случая
  2. Стратегия рекурсии, чтобы разбить проблему от начального ввода до базового случая
  3. Использование возвращенных результатов для получения окончательных результатов

Пример рекурсии

Напишите факториальную функцию, если на входе задано число.

Факториал - это ! в математике. Например:

4! = 4 * 3 * 2 * 1 👉, что можно обобщить до 👉 4! = 4 * 3!

3! = 3 * 2 * 1 👉, что можно обобщить до 👉 3! = 3 * 2!

2! = 2 * 1 👉, что можно обобщить до 👉 2! = 2* 1!

1! = 1 👉, который можно обобщить до 👉 1! = 1*0!

0! = 1

Таким образом, мы можем сделать вывод, что базовый вариант — это 0, который всегда должен возвращать 1.

Основная функция factorial должна вызываться рекурсивно, вычитая ввод на 1 при умножении на себя. Ниже приведена реализация factorial в JS (реализация должна быть аналогичной на других языках, за исключением различий в синтаксисе). Оптимизации для этой функции исключены только с целью иллюстрации рекурсии.

function factorial(n) {
  if (n === 0) return 1; // base-case
  const prevFactorial = factorial(n - 1); 
// recursive call where the function calls itself to reach base-case. In this case base-case is 0, so the input to the function should be decreasing as the function calls itself. 
  return n * prevFactorial;  // using the returned results from previous recursive call to ultimately come up with answer;
}

Подводные камни, на которые следует обратить внимание…

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

  1. Бесконечный цикл: это может произойти, когда рекурсивная функция вызывается повторно без определенного базового случая или без возможности добраться до базового случая. Так часто бывает и программа жалуется на переполнение стека.
  2. Ошибка при выполнении рекурсии: это может произойти, когда рекурсивная функция возвращает неожиданные результаты. Знание того, что возвращается на каждом шаге рекурсивной функции, важно, чтобы следующий шаг функции был готов к результатам предыдущей функции и использовал их для вычисления результата.
  3. Разочарование… Не расстраивайтесь, рекурсия. Найдите закономерности того, как проблема может разбиваться на более мелкие проблемы. Иногда написание итеративной версии или объяснение решения простым английским языком помогает увидеть закономерность. Рекурсия — это ИСКУССТВО. Практикуйте это, поскольку это имеет основополагающее значение для элегантного решения сложных проблем.

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