Базовое введение в рекурсию
Я только недавно начал то, что, надеюсь, станет путешествием на всю жизнь в мир программирования, и мой первый набег — на JavaScript. Одна из первых концепций, с которой я столкнулся, называется рекурсия, и я нашел эту тему особенно интересной и забавной. Я слышал, что один из лучших способов учиться — учить. Итак, в качестве упражнения я хотел бы дать небольшой урок по рекурсии. Насколько я понимаю, концепция рекурсии относительно универсальна, но этот короткий урок будет проходить через призму JavaScript, так как это единственный язык, с которым я знаком на момент написания. Надеюсь, это не исказит мое понимание и объяснение концепции до неузнаваемости для тех читателей, которые уже хорошо знакомы с предметом.
Что такое рекурсия?
Теперь, некоторые быстрые исследования показали мне, что рекурсия на самом деле является концепцией из математики. У меня есть ощущение, что это справедливо для многих идей и концепций компьютерных наук, но исследование этой гипотезы выходит за рамки этого поста. Оксфордский словарь определяет рекурсию как «повторяющееся применение рекурсивной процедуры или определения». Теперь, если вы никогда раньше не имели дело с рекурсией, это может сразу показаться вам немного странным. Определение рекурсии включает слово или, по крайней мере, понятие рекурсии. Забавно, но это вполне уместно, и если мы копнем немного дальше и посмотрим на определение рекурсивного, мы получим более прямой ответ. Снова заглянув в Оксфордский словарь, мы видим, что рекурсивный имеет определение, которое гораздо полезнее, чем первое: «относящийся к повторному применению правила, определения или процедуры к последовательным результатам или включающий их». Итак, если ваша математическая задача требует, чтобы вы снова и снова выполняли одну и ту же операцию для получения ответа, который вы получаете каждый раз, это рекурсия.
Однако в Оксфордском словаре приводится второе определение рекурсивного, относящееся непосредственно к вычислениям: «относящийся к программе или подпрограмме, часть которой требует применения целого, так что ее явная интерпретация обычно требует многих последовательных выполнений». Чтобы объяснить это простым языком, пример рекурсивного кода — это тот, который перед завершением выполнения вызывает другой экземпляр того же самого кода. В JavaScript вызов функции известен как «вызов» функции. Итак, рекурсивная функция — это функция, которая для полного завершения работы вызывает саму себя один или несколько раз.
В качестве упражнения мне было поручено создать рекурсивную версию метода сокращения массива. Функция JavaScript reduce состоит в том, чтобы взять массив для перебора, функцию итератора, которая будет выполняться для каждого значения массива, и построить значение аккумулятора с каждой итерацией. Глядя на мою рекурсивную версию, мы можем видеть, где будут происходить рекурсивные вызовы и как они затем будут передавать информацию по цепочке вызовов до тех пор, пока не будет возвращен окончательный массив данных.
При создании рекурсивной функции важно создать точку остановки или базовый случай прямо в верхней части функции (строки 5–8). Здесь я использую оператор if, чтобы проверить, пуст ли массив, который я повторяю. Это будет тот случай, когда я закончу свои итерации, поскольку каждая из итераций выполняется с немного меньшей версией исходного массива. Эта проверка завершения важна для того, чтобы избежать бесконечного цикла или другой ошибки, которая приводит к тому, что функция не может правильно вернуть желаемое значение.
В случае рекурсии (строки 9–14) рекурсия действительно происходит. В строках 12 и 14 мы видим операторы возврата, которые вызывают функцию, внутри которой они находятся. Это рекурсивные вызовы. В этом примере каждый из этих вызовов будет выполнять оператор if, чтобы проверить, пуст ли теперь массив, затем, если это так, вернуть значение встроенного аккумулятора, а в противном случае они будут выполнять функцию итератора ввода, предоставленную в качестве аргумента исходному вызову функции, и снова вызовите рекурсивный вызов, пока массив значений не будет исчерпан, и значение аккумулятора, которое было построено по пути, будет возвращено вверх по цепочке вызовов функций, чтобы, наконец, быть возвращено самой верхней функцией.
В заключение, рекурсия — это способ для программиста настроить сценарий, в котором функция может многократно вызывать себя для выполнения одной и той же задачи снова и снова, пока не будет выполнено условие завершения. Это может помочь улучшить код несколькими способами, включая сокращение времени выполнения и улучшение общей читабельности кода. Рекурсия — это забавная концепция, с которой можно поиграться. Я с нетерпением жду возможности углубить свое собственное понимание рекурсии по мере того, как я все глубже и глубже погружаюсь в JavaScript и другие языки программирования.
