Одна из программных конструкций, с которой я всегда борюсь, — это рекурсия. Концепция рекурсии на самом деле довольно проста, но я нахожу ее неинтуитивной и сложной. Часто я слышу, как люди говорят, можно ли реализовать что-то итеративно. Но зачем кому-то хотеть писать решение рекурсивно, когда вы можете написать его итеративно? Это потому, что рекурсивное решение часто обеспечивает гораздо более чистое и элегантное решение.
В настоящее время я все еще нахожусь в пути, чтобы узнать больше о рекурсии, и я надеюсь, что, поделившись своим пониманием рекурсии, я смогу глубже понять ее.
Что такое рекурсия?
Рекурсия — это способ решения проблемы путем многократного вызова самой функции. Идея состоит в том, что основная функция будет многократно вызывать себя в меньшем контексте, пока не достигнет базового случая. Базовый случай — это когда функция попадает в простой случай, когда она может просто вернуть ответ. Как только функция в верхней части стека достигает базового регистра, она передает ответ предыдущей функции, чтобы помочь этой функции вернуть ответ. В конце концов, он вернет ответ обратно в исходную функцию.
Я думаю о рекурсии как о поездке на лифте. Вы должны подниматься и спускаться на лифте, чтобы вернуться туда, откуда пришли. Поскольку функция многократно вызывает себя в рекурсии, она добавляется в стек, как будто поднимается на лифте. Затем он попадает в базовый случай, подобно тому, как лифт попадает на верхний этаж. У него нет другого выбора, кроме как вернуться вниз. Значение, возвращаемое из базового случая, возвращается вниз, когда функции выталкиваются из стека вызовов. К тому времени, когда функция возвращается к исходной функции, она находится в результатах.
Основы рекурсии
- Настройка базового случая
- Стратегия рекурсии, чтобы разбить проблему от начального ввода до базового случая
- Использование возвращенных результатов для получения окончательных результатов
Пример рекурсии
Напишите факториальную функцию, если на входе задано число.
Факториал - это !
в математике. Например:
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; }
Подводные камни, на которые следует обратить внимание…
Знайте, как разбить проблему — то есть, что является вводом рекурсивной функции каждый раз, когда она вызывается. Знайте, что является базовым случаем для рекурсивной функции, чтобы начать возвращать результаты. Знайте, какие типы результатов возвращаются вызовом функции.
- Бесконечный цикл: это может произойти, когда рекурсивная функция вызывается повторно без определенного базового случая или без возможности добраться до базового случая. Так часто бывает и программа жалуется на переполнение стека.
- Ошибка при выполнении рекурсии: это может произойти, когда рекурсивная функция возвращает неожиданные результаты. Знание того, что возвращается на каждом шаге рекурсивной функции, важно, чтобы следующий шаг функции был готов к результатам предыдущей функции и использовал их для вычисления результата.
- Разочарование… Не расстраивайтесь, рекурсия. Найдите закономерности того, как проблема может разбиваться на более мелкие проблемы. Иногда написание итеративной версии или объяснение решения простым английским языком помогает увидеть закономерность. Рекурсия — это ИСКУССТВО. Практикуйте это, поскольку это имеет основополагающее значение для элегантного решения сложных проблем.
Надеюсь, это прояснит рекурсию. Не стесняйтесь добавлять комментарии и отзывы ниже. Я буду добавлять больше концепций программирования по мере того, как буду больше узнавать об алгоритмах и структурах данных.