В этой статье будут представлены основные концепции стека и рекурсии, а также то, что происходит за кулисами для решения этого интересного алгоритма ниже:
Прежде чем погрузиться в происходящее, давайте рассмотрим две концепции, начиная с….
Куча
Стек - это концептуальная структура, состоящая из набора однородных элементов и основанная на принципе «последний пришел - первым вышел» (LIFO) или «первым пришел - последний вышел» (FILO). Это часто используемый абстрактный тип данных с двумя основными операциями, а именно push и pop. Push и pop выполняются на самом верхнем элементе, который был добавлен в стек самым последним. Операция push добавляет элемент в стек, а операция pop удаляет элемент из верхней позиции. Концепция стека используется при программировании и организации памяти компьютеров.
Рекурсия
Лучше всего объяснить это тем, что рекурсивная функция - это функция, которая должна возвращать либо:
- значение "базового случая"
- Результат вызова самого себя (также может быть несколько вызовов самого себя)
Когда вы вызываете рекурсивную функцию, если она не достигает базового случая, она будет продолжать вызывать себя (часто с немного разными аргументами каждый раз), пока не вернет базовый случай.
Как только функция вернет базовый случай, рекурсия начнет разворачиваться. На этапе разворачивания возвращаемые значения предыдущих рекурсивных вызовов делают более интересную работу.
Лучший способ визуализировать рекурсию - представить себе, что у вас есть стек вызовов функций, и каждый раз, когда функция вызывает себя, она создает еще одну копию себя с новыми аргументами и помещает эту копию поверх стека. Обычно есть обозначенный указатель на то, где находится каждый вызов. Указатель программы перемещается на копию (но сохраняет ссылку на то, что было в предыдущем вызове). И он продолжает наращивать стек с новыми копиями функции, пока не достигнет базового случая (когда функция наконец вернет свое значение).
Фаза `` раскрутки '' - это когда функции начинают возвращаться (после того, как был достигнут один из базовых случаев), и все `` копии '' функции просто выталкиваются из вершины стека одна за другой после FILO / LIFO . Каждый раз программа будет продолжать работать с того места, где она находилась в каждом стеке вызовов.
Хорошо, вернемся к алгоритму:
Алгоритм представляет собой простую реализацию следующего рекуррентного соотношения, используемого для вычисления «x» в степени «y», где «x» и «y» являются целыми числами.
Допустим, сгенерированное входное значение рекурсии реализовано с помощью recusion (2,5).
x = 2 и y = 5 и ниже - это то, что я смоделировал на своем компьютере, чтобы отображать значение y при каждом последующем вызове функции.
Алгоритм, рекурсия (2,2,), рекурсия (2,1) вычисляются несколько раз. Чтобы избежать одних и тех же вычислений, мы сохраняем результат во временной переменной при выполнении рекурсивного вызова и многократно используем это значение переменной по порядку.
Каждый вызов функции будет помещен в мэйнфрейм стека, следуя порядку «первым пришел - первым вышел» (FILO) с каждым разом, когда y будет вычитаться на 1. Как только y станет равным 0, вернуть (1) или если стек заполнен (y = -1 ) и выгружаем функции, начиная сверху и умножая возвращаемое значение на x, пока не вернемся к основной функции. Окончательное значение 32 = 2 * 2 * 2 * 2 * 2 = 2 ^ 5.
