Рекурсия в программировании


Оглавление (нажмите, чтобы открыть):

Рекурсия в программировании. Функции

В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функциюB , а функция A — функцию B. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

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

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

Имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивается выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти. Однако, далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений — язык Scheme (диалект языка Lisp), описание которого содержит все необходимые сведения.

Любую рекурсивную функцию можно заменить циклом и стеком.

Описание типа данных может содержать ссылку на саму себя. Подобные структуры используются при описании списков и графов. Пример описания списка (C++):

element_of_list *next; /* ссылка на следующий элемент того же типа */

int data; /* некие данные */

Рекурсивная структура данных зачастую обуславливает применение рекурсии для обработки этих данных.

Рекурсия и стек

Вернёмся к функциям и изучим их более подробно.

Наша первая тема будет рекурсия.

Если вы не новичок в программировании, то, возможно, уже знакомы с рекурсией и можете пропустить эту главу.

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

В процессе выполнения задачи в теле функции могут быть вызваны другие функции для выполнения подзадач. Частный случай подвызова – когда функция вызывает сама себя. Это как раз и называется рекурсией.

Два способа мышления

В качестве первого примера напишем функцию pow(x, n) , которая возводит x в натуральную степень n . Иначе говоря, умножает x на само себя n раз.

Рассмотрим два способа её реализации.

Итеративный способ: цикл for :

Рекурсивный способ: упрощение задачи и вызов функцией самой себя:

Обратите внимание, что рекурсивный вариант отличается принципиально.

Когда функция pow(x, n) вызывается, исполнение делится на две ветви:

  1. Если n == 1 , тогда всё просто. Эта ветвь называется базой рекурсии, потому что сразу же приводит к очевидному результату: pow(x, 1) равно x .
  2. Мы можем представить pow(x, n) в виде: x * pow(x, n — 1) . Что в математике записывается как: x n = x * x n-1 . Эта ветвь – шаг рекурсии: мы сводим задачу к более простому действию (умножение на x ) и более простой аналогичной задаче ( pow с меньшим n ). Последующие шаги упрощают задачу всё больше и больше, пока n не достигает 1 .

Говорят, что функция pow рекурсивно вызывает саму себя до n == 1 .

Например, рекурсивный вариант вычисления pow(2, 4) состоит из шагов:

  1. pow(2, 4) = 2 * pow(2, 3)
  2. pow(2, 3) = 2 * pow(2, 2)
  3. pow(2, 2) = 2 * pow(2, 1)
  4. pow(2, 1) = 2

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

Рекурсивное решение задачи обычно короче, чем итеративное.

Используя условный оператор ? вместо if , мы можем переписать pow(x, n) , делая код функции более лаконичным, но всё ещё легко читаемым:

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

Максимальная глубина рекурсии ограничена движком JavaScript. Точно можно рассчитывать на 10000 вложенных вызовов, некоторые интерпретаторы допускают и больше, но для большинства из них 100000 вызовов – за пределами возможностей. Существуют автоматические оптимизации, помогающие избежать переполнения стека вызовов («оптимизация хвостовой рекурсии»), но они ещё не поддерживаются везде и работают только для простых случаев.

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

Контекст выполнения, стек

Теперь мы посмотрим, как работают рекурсивные вызовы. Для этого заглянем «под капот» функций.

Информация о процессе выполнения запущенной функции хранится в её контексте выполнения (execution context).

Контекст выполнения – специальная внутренняя структура данных, которая содержит информацию о вызове функции. Она включает в себя конкретное место в коде, на котором находится интерпретатор, локальные переменные функции, значение this (мы не используем его в данном примере) и прочую служебную информацию.

Один вызов функции имеет ровно один контекст выполнения, связанный с ним.

Когда функция производит вложенный вызов, происходит следующее:

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

Разберёмся с контекстами более подробно на примере вызова функции pow(2, 3) .

pow(2, 3)

В начале вызова pow(2, 3) контекст выполнения будет хранить переменные: x = 2, n = 3 , выполнение находится на первой строке функции.

Можно схематически изобразить это так:

Это только начало выполнения функции. Условие n == 1 ложно, поэтому выполнение идёт во вторую ветку if :

Значения переменных те же самые, но выполнение функции перешло к другой строке, актуальный контекст:

Чтобы вычислить выражение x * pow(x, n — 1) , требуется произвести запуск pow с новыми аргументами pow(2, 2) .

pow(2, 2)

Для выполнения вложенного вызова JavaScript запоминает текущий контекст выполнения в стеке контекстов выполнения.

Здесь мы вызываем ту же функцию pow , однако это абсолютно неважно. Для любых функций процесс одинаков:

  1. Текущий контекст «запоминается» на вершине стека.
  2. Создаётся новый контекст для вложенного вызова.
  3. Когда выполнение вложенного вызова заканчивается – контекст предыдущего вызова восстанавливается, и выполнение соответствующей функции продолжается.

Вид контекста в начале выполнения вложенного вызова pow(2, 2) :

Новый контекст выполнения находится на вершине стека (и выделен жирным), а предыдущие запомненные контексты – под ним.

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

pow(2, 1)

Процесс повторяется: производится новый вызов в строке 5 , теперь с аргументами x=2 , n=1 .


Создаётся новый контекст выполнения, предыдущий контекст добавляется в стек:

Теперь в стеке два старых контекста и один текущий для pow(2, 1) .

Выход

При выполнении pow(2, 1) , в отличие от предыдущих запусков, условие n == 1 истинно, поэтому выполняется первая ветка условия if :

Вложенных вызовов больше нет, поэтому функция завершается, возвращая 2 .

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

Возобновляется обработка вызова pow(2, 2) . Имея результат pow(2, 1) , он может закончить свою работу x * pow(x, n — 1) , вернув 4 .

Восстанавливается контекст предыдущего вызова:

Самый внешний вызов заканчивает свою работу, его результат: pow(2, 3) = 8 .

Глубина рекурсии в данном случае составила 3.

Как видно из иллюстраций выше, глубина рекурсии равна максимальному числу контекстов, одновременно хранимых в стеке.

Обратим внимание на требования к памяти. Рекурсия приводит к хранению всех данных для неоконченных внешних вызовов в стеке, и в данном случае это приводит к тому, что возведение в степень n хранит в памяти n различных контекстов.

Реализация возведения в степень через цикл гораздо более экономна:

Итеративный вариант функции pow использует один контекст, в котором будут последовательно меняться значения i и result . При этом объём затрачиваемой памяти небольшой, фиксированный и не зависит от n .

Любая рекурсия может быть переделана в цикл. Как правило, вариант с циклом будет эффективнее.

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

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

Рекурсивные обходы

Другим отличным применением рекурсии является рекурсивный обход.

Представьте, у нас есть компания. Структура персонала может быть представлена как объект:

Другими словами, в компании есть отделы.

Отдел может состоять из массива работников. Например, в отделе sales работают 2 сотрудника: Джон и Алиса.

Или отдел может быть разделён на подотделы, например, отдел development состоит из подотделов: sites и internals . В каждом подотделе есть свой персонал.

Также возможно, что при росте подотдела он делится на подразделения (или команды).

Например, подотдел sites в будущем может быть разделён на команды siteA и siteB . И потенциально они могут быть разделены ещё. Этого нет на картинке, просто нужно иметь это в виду.

Теперь, допустим, нам нужна функция для получения суммы всех зарплат. Как мы можем это сделать?

Итеративный подход не прост, потому что структура довольно сложная. Первая идея заключается в том, чтобы сделать цикл for поверх объекта company с вложенным циклом над отделами 1-го уровня вложенности. Но затем нам нужно больше вложенных циклов для итераций над сотрудниками отделов второго уровня, таких как sites … А затем ещё один цикл по отделам 3-го уровня, которые могут появиться в будущем? Если мы поместим в код 3-4 вложенных цикла для обхода одного объекта, то это будет довольно некрасиво.

Давайте попробуем рекурсию.

Как мы видим, когда наша функция получает отдел для подсчёта суммы зарплат, есть два возможных случая:

  1. Либо это «простой» отдел с массивом – тогда мы сможем суммировать зарплаты в простом цикле.
  2. Или это объект с N подотделами – тогда мы можем сделать N рекурсивных вызовов, чтобы получить сумму для каждого из подотделов, и объединить результаты.

Случай (1), когда мы получили массив, является базой рекурсии, тривиальным случаем.

Случай (2), при получении объекта, является шагом рекурсии. Сложная задача разделяется на подзадачи для подотделов. Они могут, в свою очередь, снова разделиться на подотделы, но рано или поздно это разделение закончится, и решение сведётся к случаю (1).

Рекурсия

Рекурсия — состоит в определении, описании, изображении какого-либо объекта или процесса внутри самого этого объекта или процесса. Это ситуация, когда объект является частью самого себя.

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

Процедура func() вызывается с параметром 3. В ней содержится вызов процедуры func() с параметром 2. Предыдущий вызов еще не завершился, поэтому создается еще одна процедура и до окончания ее работы func(3) свою работу приостанавливает. Процесс вызова заканчивается, когда параметр равен 0. В этот момент одновременно выполняются 4 экземпляра процедуры.

Количество одновременно выполняемых процедур называют глубиной рекурсии .

Последняя вызванная процедура func(0) выведет число 0 и закончит свою работу. После этого управление возвращается к процедуре, которая ее вызвала: func(1) и выводится число 1. И так далее пока не завершатся все процедуры.

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

Сложная рекурсия

Возможна чуть более сложная схема: функция A вызывает функцию B, а та в свою очередь вызывает A. Это называется сложной рекурсией . При этом оказывается, что описываемая первой процедура должна вызывать еще не описанную. Чтобы это было возможно, требуется использовать описание функции B до ее использования.
Пример : вычислить значение выражения

Префиксная и постфиксная форма записи

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

Cравнение цикла и рекурсии с точки зрения производительности приложений

Серия контента:

Этот контент является частью # из серии # статей: Комментарий

Этот контент является частью серии: Комментарий

Следите за выходом новых статей этой серии.

Написание кода с оптимальной производительностью

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

Рекурсия

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

  • Головная рекурсия— рекурсивный вызов выполняется ближе к началу метода и является одним из первых обрабатываемых объектов. Поскольку он вызывает сам себя, ему приходится полагаться на результаты предыдущей операции, помещенной в стек вызовов. Из-за использования стека вызовов существует вероятность переполнения стека, если стек вызовов недостаточно велик.
  • Концевая рекурсия— рекурсивный вызов выполняется в конце и является последней строкой обрабатываемого кода. Этот метод не использует стек вызовов независимо от глубины рекурсии.

В математике рекурсия распространена достаточно широко, поэтому проще будет объяснить ее на примере рекурсивного вызова. Выражение 5! (факториал числа 5) можно записать следующим способом:

5!
5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 2 * 1

В листинге 1 приведен пример вычисления 5! с помощью головной рекурсии.

5!
5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 2 * 1

В листинге 1 приведен пример вычисления 5! с помощью головной рекурсии.

Листинг 1. Листинг 1

Каждый рекурсивный вызов должен быть завершен и помещен в стек вызовов до расчета факториала. Java™ будет интерпретировать каждый вызов метода getFactorial следующим образом (каждая строка представляет объект, находящийся в стеке вызовов):


5 * getFactorial(4)
5 * (4 * getFactorial(3))
5 * (4 * (3 * getFactorial(2)))
5 * (4 * (3 * (2 * getFactorial(1))))
5 * (4 * (3 * (2 * 1)))
120

В листинге 2 приведен пример вычисления 5! с помощью концевой рекурсии.

Листинг 2. Листинг 2

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

Листинг 3. Листинг 3

Языки программирования предоставляют циклы нескольких разных типов, очень хорошо знакомых большинству программистов. В языке программирования Java имеются циклы for, do и while. Цикл — это многократное исполнение нескольких операторов. Циклы не заносят данные в стек вызовов независимо от числа исполнений цикла. Важным отличием циклов от рекурсивных функций является тот факт, что циклы используют для подсчета числа исполнений итератор, а рекурсивные функции для определения момента выхода должны выполнять сравнение результатов. Другим важным отличием является возможность применения в циклах фильтров и прочих селекторов. Примером такой ситуации может служить цикл foreach.

Что лучше?

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

Контрольные примеры

Приведенные ниже контрольные примеры запускались в 64-разрядной среде исполнения IBM Java Runtime Environment (JRE) 7.0.4.0 (с аргументом командной строки -Xms256m -Xmx256m -Dcom.ibm.tools.attach.enable=no). Чтобы среда исполнения не тратила время на расширение и сжатие кучи, JRE запускалась с фиксированным размером кучи 256 МБ. Отключение API Attach не позволяет JRE запускать приложения-агенты (обычно используемые для мониторинга), что нормализует производительность в каждом тесте. При увеличении стека вызовов для инициализации стека и поддержания его на уровне 3 МБ использовался аргумент командной строки -Xss3m -Xssi3m.

Вычисление суммы

При суммировании чисел цикл показал значительно более высокую производительность, а концевая рекурсия оказалась быстрее головной. При увеличении стека вызовов Java до 3 МБ головная рекурсия сравнялась по скорости с концевой, но все же не смогла догнать цикл.

Рисунок 1. Рисунок 1. Вычисление суммы

Вычисление факториала

Этот примечательный пример иллюстрирует зависимость результатов от используемых операторов. При использовании простого типа данных int лучшие результаты во всех случаях получились для цикла. Применение типа int ограничивает величину результата до 32-разрядного целого числа со знаком. Для больших факториалов можно использовать тип данных BigInteger, но такая конструкция будет более затратной. Результаты применения BigInteger показали, что использование головной рекурсии в паре с концевой обеспечивает лучшее быстродействие, чем чисто концевая рекурсия или цикл.

Рисунок 2. Рисунок 2. Вычисление факториала

Области применения рекурсии

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

В задаче, получившей название Ханойская башня, даны три стрежня и диски разного размера, которые в исходном состоянии надеты на первый стержень в виде башни. Задача состоит в том, чтобы перенести башню на другой стержень, при этом запрещается класть большой диск на маленький. Эту замечательную задачу можно легко решить с помощью рекурсии за 2n — 1 ходов, где n — число дисков.

Например, возьмем четыре диска и попытаемся перенести их со стержня A на стержень C, используя стержень B для временного хранения. С помощью описанной ниже рекурсивной функции это может быть выполнено за 15 ходов. Процесс решения можно визуализировать этим апплетом. Функция вызывается (2n * 2) – 1, или 31 раз. Причина, по которой число вызовов функции не равно числу ходов, кроется в том, что для обработки ходов необходимо установить стек вызовов. В этом примере используется головная рекурсия (листинг 4).

Листинг 4. Листинг 4

Результат для четырех дисков показан в листинге 5.

Листинг 5. Листинг 5

Ханойская башня — широко распространённая задача, которую можно решить с помощью рекурсии. Однако не все задачи столь очевидны, многие из них требуют времени на анализ и решение. Ханойскую башню можно решить и с помощью циклов, однако это потребует использования нескольких различных циклов и итераторов. Это решение будет работать дольше и потребует большего объема кода.

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

Листинг 6. Листинг 6

Заключение

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

Рекурсия

В математике строгое определение некоторых понятий может опираться на то же понятие. Такие определения называют рекурсивными или индуктивными. Например, рекурсивно определяется факториал:

Данное определение состоит из двух утверждений. Первое утверждение носит название базисного. Базисное утверждение нерекурсивно. Второе утверждение носит название рекурсивного или индуктивного. Оно строится так, чтобы полученная в результате повторных применений цепочка определений сходилась к базисному утверждению.

В программировании рекурсивной называется подпрограмма, которая в процессе выполнения вызывает сама себя.

Различают два вида рекурсии подпрограмм:

  • 1) прямая или явная рекурсия — характеризуется существованием в теле подпрограммы оператора обращения к самой себе;
  • 2) косвенная или неявная рекурсия — образуется при наличии цепочки вызовов других подпрограмм, которые в конечном итоге приведут к вызову исходной.
Мастер Йода рекомендует:  Программист создал приложение, превращающее любой Android-смартфон в iPhone X

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

Фрейм активации включает:

  • • копии всех локальных переменных подпрограммы;
  • • копии параметров-значений;
  • • четырехбайтовые адреса параметров-переменных и параметров- констант;
  • • копию строки результата (для функций типа string);
  • • служебную информацию — более 12 байт, точный размер этой области зависит от внутренней организации подпрограмм.

Пример 5.11. Разработать программу определения наибольшего общего делителя двух чисел, используя алгоритм Евклида.

Нерекурсивный вариант этого алгоритма был рассмотрен в примере 1.2. Рекурсивный вариант будем строить исходя из двух утверждений.

Базисное утверждение: если два числа равны, то их наибольший общий делитель равен этим числам.

Рекурсивное утверждение: наибольший общий делитель двух чисел равен наибольшему общему делителю их разности и меньшего из чисел.

Рекурсивная подпрограмма может быть реализована и как процедура, и как функция. При реализации в виде процедуры список параметров кроме чисел А и В включает параметр-переменную R. Через этот параметр процедура возвращает результат (рис. 5.10, а).

Рис. 5.10. Схема алгоритма Евклида: а — с использованием рекурсивной процедуры; б— с использованием рекурсивной функции

Текст программы, реализующий вариант с рекурсивной процедурой, представлен ниже.

Procedure nod(a,b:integer; var r:integer); begin

if a=b then r:=a else if a> then nod(a-b,b,r) else nod(a,b-a,r)

ReadLn(a,b); nod(a,b, r) ;

При выполнении программы фреймы активации будут размещаться в стеке — специальным образом организованной памяти. Например, для д=12ий = 8в момент завершения нерекурсивной третьей активации стек будет выглядеть, как показано на рис. 5.11 (запись в стек идет двойными словами, т.е. по 4 байта).

Рис. 5.11. Заполнение стека при выполнении рекурсивной подпрограммы

Если реализовать вариант с рекурсивной функцией (см. рис. 5.10, б), то фрейм активации уменьшится, так как сократится список параметров. Соответствующая программа будет выглядеть следующим образом:

begin if a=b then nod:=a else

if a> then nod:=nod(a-b,b)

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

Пример 5.12. Разработать рекурсивную подпрограмму «переворота» строки (первая буква должна стать последней, вторая — предпоследней и Т.Д.).

Можно предложить два способа разворота строки.

Первый способ заключается в последовательном отсечении начального элемента и добавлении его в конец результирующей строки.

Второй способ базируется на последовательной перестановке элементов: первого с последним, второго — с предпоследним и т.д. Перестановки должны прекратиться, когда дойдем до середины строки, иначе вновь поставим элементы на исходные места.

Вариант с отсечением и дописыванием:

Function reversel(const st:string):string;

if length (st)=0 then reverserl: = » else


reversel(copyist, 2, length(st) -1)) +st[l];

Определим размер фрейма активации:

V— 4 (адрес параметра) + 256 (результат-строка) +

Вариант с использованием перестановок’.

Procedure reverse2(var ss:string; n:integer);

Var temp:char; begin

Следовательно, второй вариант предпочтительнее.

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

Причиной бесконечной рекурсии может быть не только ошибка в программе, но и обработка некорректных данных.

Пример 5.13. Разработать программу определения корней уравнения у = х 2 — 2 на заданном отрезке методом половинного деления.

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

Базисное утверждение: если абсолютная величина функции в середине отрезка не превышает заданного значения погрешности, то координата середины отрезка и есть корень.

Рекурсивное утверждение: корень расположен между серединой отрезка и тем концом, значение функции в котором по знаку не совпадает со значением функции в середине отрезка (рис. 5.12).

Рис. 5.12. Рекурсивный алгоритм определения корней уравнения

procedure root(a,b,eps:real; var r:real); var f,x:real; begin

if abs(f) 0 then root(x,b,eps,r) else root (a,x,eps,r)

WriteLn( 1 Root x=’,x:9:7);

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

При объявлении косвенно рекурсивных подпрограмм возникает проблема; их описания принципиально не удается расположить так, чтобы избежать обращения к еще не описанным ресурсам, как того требуют правила объявления ресурсов Delphi Pascal. В этом случае используют специальную директиву forward, которая позволяет выполнять предописание: сначала записывают заголовки подпрограмм с параметрами, за которыми вместо тела подпрограммы следует forward; затем описывают тела этих подпрограмм (причем параметры второй раз можно уже не описывать).

Например, описание процедур А и В, которые рекурсивно вызывают друг друга (рис. 5.13), можно выполнить следующим образом:

procedure B(j:byte); forward; procedure A(j:byte);

begin. В (i) ;. end; procedure B;

Рис. 5.13. Пример взаимно рекурсивных подпрограмм

Пример 5.14. Разработать программу проверки чередования букв и цифр в заданной строке (первый символ — обязательно буква).

  • • строка допустима, если она пустая;
  • • строка не допустима, если в ней обнаружен недопустимый символ.

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

Var s: shortstring;

function f_char(var st:shortstring;

i:word):boolean; forward; function f_value(var st:shortstring; i:word):boolean; begin

if i>length(st) then f_value:=true else

if(st[i] in[‘0 1 .. 1 9’])

then f_value:=f_char(st,i+1) else f_value:=false;

function f_char; begin

if i>length(st) then f_char:=true else

if(st[i] in[’A’..’Z’,’a’..’z ’ ]) then f_char:=f_value(st,i+1) else f_char:=false;

WriteLn( 1 Введите строку:’);

ReadLn(s); if f_char(s,l) then

WriteLn(‘The string is correct.’) else WriteLn(‘ The string is not correct.’);

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

Операторы, которые на схеме помечены как «операторы после вызова», выполняются после возврата управления из рекурсивно вызванной подпрограммы. Если попытаться изобразить последовательность действий при линейной рекурсии, то она будет выглядеть, как это показано на рис. 5.15.

Рис. 5.14. Структура подпрограммы с линейной рекурсией

Рис. 5.15. Рекурсивное погружение и рекурсивный выход при линейной рекурсии

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

Пример 5.15. Разработать программу, которая выводит из заданного массива, завершающегося нулем, сначала положительные значения, а затем отрицательные в любом порядке. Между положительными и отрицательными элементами массива вывести три звездочки.

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

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

Type mas=array[1..10] of real;

procedure print(var x:mas; i:integer);

if x[i]=0 then WriteLn(‘*** 1 ) else begin

if x[i]>0 then WriteLn(i,x[i]);

if x[i] m then begin for i:=l to ш do Write(pole[i]); Write(‘ ’); end else

for i:=l to m-n+1 do begin

for j:=l to m-n+1 do if joi then begin

Рис. 5.17. Схема алгоритма подпрограммы формирования перестановок

Определим размер фрейма активации: параметры V = 2 ? 4 + 4 + 4;

локальные переменные V2 = т + 3 • 2; служебная информация У> * 12, откуда,

Максимальное количество одновременно существующих активаций равно (т + 1). Соответственно максимальный объем используемой памяти стека

Так, для т = 5, V= 210 (байт).

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

Рекурсия в программировании

Довольно давно, в программировании появился термин «рекурсия«, что означает вызов функции (или же процедуры) непосредственно из самой себя. Есть простая (непосредственная) рекурсия или рекурсия, которая работает через другие процедуры и функции (такой вид называется косвенной, сложной рекурсией).


В повседневной и научной жизни мы часто сталкиваемся с рекурсией. Например:

  • треугольник Серпинского;
  • эффект Дросте;
  • вычисление факториала.

Самый простой способ понаблюдать за рекурсией – это навести вэб-камеру на монитор вашего персонального компьютера, конечно же её включив.

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

Кроме того, в функциональных языках в чистом виде (к ним относятся Пролог, Haskell) невозможно задать цикл синтаксически, поэтому рекурсия является единственным доступным средством задания повторяющихся вычислений. Но иногда, следует избегать рекурсивных конструкций в программных модулях, потому что они могут стать причиной излишне глубокой рекурсии. В языках С++/С# функции имеют возможность вызова самих себя.

Дадим определение рекурсивной функции— это функция, в теле которой оператор вызывает функцию, которую содержит данный оператор.

Самым распространенным примером рекурсии служит известная функция вычисления факториала factоr(). Факториал некоторого числа это произведение чисел от 1 до этого числа.

Рекурсия в программировании

  • Количество способов перестановки n объектов равно n! (перестановки)
  • n! определяется таким способом: если n = 0, то n! = 1; если n > 0, то n! = n * (n-1)!

Функция, вычисляющая факториал:

Требования рекурсии

  1. Простой базовый случай, или терминальный сценарий, или терминальное условие. Простыми словами, когда остановиться. В нашем примере это была 1: мы остановили вычисление факториала, когда достигли 1.
  2. Правило двигаться по рекурсии, углубляться. В нашем случае, это было n * factorial(n-1) .

Ожидание умножения

Ничего не умножается, пока мы спускаемся к базовому случаю factorial(1) . Затем мы начинаем подниматься обратно, по одному шагу.

Примечание

Заметьте, что 0! это 1, а простой базовый случай для n! это 0! В этом уроке мы пропустили такой случай, чтобы сократить рекурсию на один вызов и на одну коробку, поскольку 1 * 1 — это, в любом случае — 1.

Просто ради забавы

У программистов есть одна шутка: «Чтобы понять рекурсию, нужно понять рекурсию». Google, кажется, любит такие шутки. Попробуйте погуглить «рекурсия» и зацените верхний результат поиска 😉

Рекомендуем посмотреть

Опциональный текст

Опциональные видео

Транскрипт урока

У нас уже есть функция surfaceAreaCalculator , которая принимает один аргумент — радиус — и возвращает площадь поверхности соответствующей сферы, используя формулу 4 * pi * r 2. Помните, мы можем представить функции ящиками: кладём что-то в ящик, она производит какие-то действия и выплёвывает результат.

Некоторые ящики не принимают ничего, другие ничего не выплёвывают, а третьи вообще ничего не делают. Но мы сейчас заинтересованы в ящиках, подобных surfaceAreaCalculator , которая принимает что-то, вычисляет и возвращает результат.

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

Ещё польза в том, что теперь код проще понять. Сравните это:

Первый вариант намного приятней и проще, особенно для того, кто только что увидел этот код. Первый вариант отвечает на вопрос «что», второй — на вопрос «как».

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

Вместо умножения радиуса на радиус, мы вызовем функцию вычисления квадрата и передадим ей радиус. Очевидно — всё, что делает функция вычисления квадрата, это «принимает число и возвращает его квадрат»;

Давайте отследим шаги и посмотрим, что происходит, когда мы запускаем нашу программу. Мы создаём константу surfaceOfMars и пытаемся сохранить в нее значение, которое возвращает функция surfaceAreaCalculator , когда она вызывается с числом 3390 в качестве аргумента.

3390 внутри функции известно как radius . Функция хочет умножить числа и выполнить возврат, но ей нужно знать последнее число, ей требуется вызвать функцию square и передать этот радиус. square принимает один аргумент — это число 3390, в нашем случае, и внутри функции square оно известно как n .

square хочет умножить n на n и сделать возврат. Ей никто не мешает и она делает это умножение и возврат. Мы снова внутри surfaceAreaCalculator , который в прямом смысле ждал, пока функция square закончит своё дело. И теперь у нас есть результат вызова square . Он заменяет вызов, поэтому теперь становится возможным завершить умножение и вернуть ответ.

Ответ возвращается и сохраняется в surfaceOfMars .

Так что функции могут вызывать другие функции. Функция не знает и не напрягается по поводу того, что она была вызвана другой функцией. Возможно, она была вызвана другой функцией, которая так же была вызвана ещё какой-то функцией! Не так важно, при условии, что вычисление возвращается и заканчивает свою работу.

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

Получается шесть уникальных комбинаций из трёх книг. Из четырёх — 24 комбинации. Из 13 — почти столько же сколько людей на планете. 25 книг? Вариантов их перестановки больше, чем атомов во Вселенной.

Вообще, существует n! вариантов перестановки n книг. Факториал означает — умножить все числа от 1 до n. Так что, 3! это 1 * 2 * 3. Давайте напишем функцию факториала.

Ой, подождите. Мы не знаем значение n изначально, в этом вся проблема. Хмм… Как там делается в математике?

А, хорошо, у них там есть два варианта: если n равно 0, тогда факториал — 1, это просто. Но если n не равно 0, тогда факториал — n*(n-1)!

Давайте попробуем вот так:

Это может показаться странным. Мы вызываем функцию из функции, но… это та же самая функция!

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

Давайте это отследим: мы вызываем factorial(3) . 3 это не 1, поэтому первое условие игнорируется. Функция хочет произвести умножение чисел и вернуть ответ, но она не может — ей нужно знать второе число, для чего она вызывает factorial(3-1) или factorial(2) .

Формируется новый идентичный ящик factorial , он принимает число 2, это не 1, так что он пробует произвести умножение и вернуть ответ, но не может — ему нужно знать второе число, поэтому он вызывает factorial(1) .

Формируется новый идентичный ящик factorial , он принимает число 1, и этот ящик уже может мгновенно вернуть ответ — он возвращает 1.

1 возвращается в предыдущий ящик, умножается на 2 и ответ «2» возвращается в предыдущий ящик, умножается на 3 и ответ «6» возвращается во внешний мир и сохраняется в константе answer .

Всё это и есть рекурсия: что-то описывается через самого себя, содержит себя в своём описании. Когда дело касается математики или программирования, требуется два условия:

  1. Простой базовый случай или терминальный сценарий. Это точка в которой нужно остановиться. В нашем примере это 1: мы остановили вычисление факториала, когда получили 1.
  2. Правило передвижения по рекурсии, углубление. В нашем случае это было n * factorial(n-1) .

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

Умножение не происходит пока мы спускаемся до базового случая функции factorial(1) . А затем мы возвращаемся наверх, производя одно умножение за один шаг.

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

Иногда информация в компьютере по своей природе требует рекурсивных функций. Например, веб-страницы состоят из HTML-элементов, и одни элементы могут входить в другие. Теги в тегах в тегах. И для эффективной обработки страницы браузеру требуется рекурсивно двигаться от уровня к уровню чтобы понять, в каком именно виде нужно вывести эти элементы на экран для пользователя.

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

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

Как я поборол рекурсию: учебный детектив

В ходе изучения третьего урока по «Основам Программирования» попался пример на рекурсию. Нужно было вывести на экран последовательность чисел от 1 до 10. Здесь всё понятно: входящее значение проверяется на услови, и если «истина» — печатается число. Затем функция вызывает саму себя заново уже с новым значением (n+1).

В итоге получаем результат: 1 2 3 4 5 6 7 8 9 10


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

А результат получился таким: 11 10 9 8 7 6 5 4 3 2 1

Мало того, что напечаталась ещё и цифра 11, так вся последовательность вывелась в обратном порядке. Но самое главное — почему оно вообще печатается? Ведь при беглом взгляде на код представляется, что этого не должно быть! 10 раз оно проверялось на условие и функция запускала саму себя заново. По идее до команды вывода на печать дело не должно доходить, ведь она стоит после вызова. Только когда значение стало 11, тогда уже вызова нет, и доходит очередь до печати. И после того, как выполнена команда на печать, функция должна завершиться! Ведь после команды на печать уже нет других команд. Но реально печатается ещё 10 значений!

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

Почему я это делаю, зачем мне это надо?

Главная причина — в учебных материалах часто бывает, что теряешься и путаешься. И когда удаётся разобраться, то всегда появляется огромное желание с кем-то поделиться. Не зря ведь говорят, что когда рассказываешь, то сам ещё лучше усваиваешь. Ещё одна причина — на дворе веб 2.0! И содержание сайтов часто формируют сами пользователи. Яркий пример — Википедия. Ну и последняя — очень удобно, когда, например, в гугле можно найти разные варианты рассмотрения той или иной темы. Можно выбрать то, что тебе больше подходит. Пускай данная статья также выступает в качестве одного из вариантов объяснения рекурсии.

Кому это может быть интересно?

Конечно, вряд ли эта статья заинтересует опытных программистов. Данный материал я публикую в основном для таких же студентов-новичков. Прочитать эту статью будет особенно полезно тем, кто не имел ранее опыта программирования. От слова «совсем». Я предлагаю один из возможных вариантов изложения темы рекурсии. Или, если не полное изложение, то хотя бы изложение некоторых вопросов в этой теме. Которые ближе к начальной стадии понимания.

3 примера, 3 знания

По ходу разборок анализ вёлся на 3 примерах, которые помогли получить 3 новых сокровенных знания. В том смысле, что об этих знаниях как-то не много говорится в учебниках. Первые два примера упомянуты в начале, а просветление началось с третьего, найденного на просторах интернета в процессе гугления.

Пример 1. Первое просветление. Незаконченная операция и стек. Матрешка

Код примера приведен ниже и должен напечатать сумму чисел от 1 до 5:

Вставлено скриншотом, чтобы сохранить номера строк — на них удобно ссылаться по ходу. Также для удобства и наглядности эта картинка будет несколько раз дублироваться ниже. Мои дальнейшие комментарии будут на уровне ученического повторения пройденного материала и его применения к конкретной задаче. Поэтому ещё раз повторюсь, материал может быть интересен главным образом таким же ученикам, каким является автор этих строк. Его следует рассматривать в качестве одного из вариантов изложения темы рекурсии, точнее даже не всей темы рекурсии, а некоторых её общих, начальных вопросов.

Рассмотрим по шагам, что происходит в этой программе.

Шаг 1

В строке 16 происходит вызов функции pow. Происходит он через вызов другой команды — alert — всем нам известной команды вывода на печать. Запускается команда alert, а в качестве её значения в параметрах задаётся вызов функции pow. В параметрах вызова функции pow указывается значение 5. Можно ещё называть его стартовым, исходным значением. Таким образом, первая команда, которая исполняется — это команда alert с вызовом функции pow и передачей ей стартового параметра 5.

Шаг 2

На этом шаге запускается функция pow в строке 3:

Для начинающих программиистов есть интересное общее правило: команды исполняются последовательно, одна за одной по очереди. Здесь же получается, что вызов в 16-й строке, а сама команда запускается из 3-й. Ответ: на самом деле в 3-й строке функция как набор команд просто объявлена и описана, но здесь она ещё не запускается. А вот команда на запуск указана именно в 16-й строке. И второй момент — функция pow при запуске принимает значение 5 из вызова.

Мастер Йода рекомендует:  Основы web

Шаг 3

Пока всё просто, значение проверяется на условие: если оно равно 1, то возвращается значение 1 в команду alert. Если значение не равно 1, т.е. результат проверки false, тогда осуществляется переход в else для выполнения размещенных там команд.

Шаг 4

Здесь начинается самое интересное. А именно — здесь есть команда:

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

А происходит то, что эта команда не завершается! Она должна была вернуть (return) в исходный вызов alert какое-то значение. Но проблема в том, что у неё нет этого значения или есть только часть этого значения. На первой итерации, как уже было сказано выше, это значение равно 5. Но к пятерке должна быть добавлена ещё какая-то цифра. И чтобы вычислить эту вторую цифру функция pow запущена заново. Функция запущена заново, а предыдущая команда осталась незавершённой. Это очень важный момент, который я вначале проскочил и скорее всего могут проскочить и другие начинающие программисты.

Вопрос: если команда не завершена, то что с ней происходит? Здесь появляется понятие стека. Само слово «стек» (от английского stack — стог, куча, множество) означает некоторый набор данных. В данном случае это набор незавершённых команд, поскольку у нас тут будет не одна команда, а несколько. Все они доходят до этого места и заворачиваются заново до тех пор, пока передаваемое значение не станет равно 1. Тогда, как было сказано ранее, произойдет return значения 1 в alert.

Особенностью хранения команд в стеке является то, что заходят они в одном порядке, а выходят в обратном. Другими словами, первый вошёл, последний вышел. И наоборот: последний вошёл, первый вышел. Для иллюстрации в этом случае часто используют пример со стопкой тарелок. Тарелки кладутся одна на другую (вход), а потом снимаются, начиная с верхней, которая была положена последней. Или пример для мачо — рожок магазина для автомата. Патроны вжимаются в него и выходят обратно первыми те, которые последние, сверху. Точно также и наши команды: они по очереди входят в стек и остаются там до поры до времени. В стеке они будут размещены так:

Самая первая по времени команда pow(5-1) будет помещена в самом низу, а самая последняя pow(2-1) окажется сверху. Именно этих вещей про незавершённость команды и про стек не было в первых темах, из-за чего и произошел затор. И тем более приятно, что удалось их проштудировать самому.

Шаг 5

Не менее интересно, что происходит потом, когда значение уменьшается до 1 и происходит передача 1 в alert. Смысл этой команды понятен, но что происходит после неё?

А происходит то, что функция не останавливается, не завершается, как можно было бы подумать и как действительно тогда мне представлялось. После этой команды начинают выполняться команды из стека, незавершённые команды. Они были запущены, они начали выполняться, но не могли закончить своё выполнение, поскольку их прерывал повторный запуск функции. И вот когда этого повторного запуска уже нет, тогда они и заканчивают своё выполнение. Здесь хорошую иллюстрацию подсказал Женя Жилинский с форума GeekBrains — записать исполнение этого кода матрёшкой, где следующий вызов является «вложенной функцией в предыдущую».

5 + pow(x-1) = 5 + ( 4 + pow(x-1) )= 5 +( 4 +( 3 + pow(x-1) ) ) = 5 +( 4 + ( 3 + (2 + pow(x-1) ) ) ) = 5 + (4 +( 3 +( 2 + 1) ) )

Сначала пружина, можно сказать, сжимается, 5 + (х-1), затем 5 + (4+(х-1)) и т.д., пока «х» не станет числом. И тогда получается простая арифметическая формула,

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

Выводы по примеру 1

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

И ещё один вывод, больше уже учебного плана: этот пример хорошо использовать на первых порах знакомства с рекурсией именно для знакомства с понятием «стек незавершенных операций».

Пример 2. Второе просветление. Запись состояния функции и незаконченность целостной функции, а не отдельной команды

Как уже было сказано ранее, эта программа выводит на экран последовательность чисел от 11 до 1.

Конструкция кода здесь немного похожа на предыдущий пример, но есть и существенные отличия. Вызов функции делается примерно также из строки после описания самой функции. Но сам вызов прямой, без другой функции (в предыдущем примере там была функция alert). Вызов функции как таковой — Print10 с передачей стартового параметра 1. Функция вывода на печать здесь тоже есть, но она представлена уже другой командой — document.write — и помещена уже в тело самой функции. Условие — не проверка на равенство единице, а проверка на то, что параметр функции должен быть меньше 11.

Общий смысл выполнения кода такой: входной параметр проверяется на условие. Если число меньше 11, то функция запускается заново и к входящему параметру добавляется 1. Когда параметр доходит до значения 11, то повторного вызова функции не происходит, а значит выполняется команда вывода на печать. Самое главное — понять, что именно выводится на печать. Засада случилась именно по этому вопросу, поскольку мне представлялось, что если параметр доходит до 11, то происходит вывод на печать этого числа и всё! Ведь дальше после команды вывода на печать уже больше нет никаких команд, значит ничего больше и не должно происходить. Программа закончена?!

Но оказывается нет! По факту она печатает еще 10 значений в нисходящем порядке. Интуитивно понимаешь, что это связано с предыдущими проверками условия, но почему это попадает на печать? Оказывается, здесь опять есть «стек» и есть незавершенные операции. Но где они, эти незавершенные операции? Если сравнивать этот пример с предыдущим, то в предыдущим довольно чётко видна незавершённая операция, это команда:

Необходимо вернуть «х», который равен определённому значению, например, 5 (или 4, или 3 и т.д.), плюс вторую часть уравнения, которую ещё нужно вычислить — для чего и запускается функция заново. Мы не можем посчитать сумму, потому что нет второй части уравнения. Именно поэтому данная операция незавершённая. Но где незавершённая операция во втором примере? Ведь здесь нет операции сложения, есть только команда повторного вызова функции:

Этот вопрос загнал меня в тупик на несколько дней. Мне показалось, что решение связано с синтаксисом кода. Куда относится команда печати — в else или вообще вне условия if? Вспомнилось правило, что условие if может быть неполным, без else. И второй момент — если в теле условия if один оператор, одна команда, то можно фигурные скобки не ставить. Таким образом, структура функции здесь выглядит так, если её расписать полностью:

Условие if в данном случае неполное, в нём нет второй части else, или она пустая. На форуме GeekBrains обратили внимание на то, что за пустой else могут уволить с работы! А поскольку я ещё не работаю программистом, то в данном случае могу себе позволить рискнуть. И далее, команда document.write к результатам проверки условия отношения не имеет. Отсюда важное следствие — команда вывода на печать будет выполняться всегда, независимо от результатов проверки условия if !

Всё это немного прояснило ситуацию, но решения не принесло. Всё выглядело так — 10 раз проверялось условие и функция запускалась заново, после чего печаталось значение 11 и на этом программа должна была завершиться. В упор не видно было, где здесь незавершённая команда — все команды отрабатывают, все завершаются. В результате долгого гугления решение нашлось на стороннем ресурсе — на сайте Тараса Диканева. У него есть страница, специально посвящённая теме рекурсии. Но готового ответа там нет, его подсказал сам автор сайта в индивидуальном общении. А именно:

«Каждый раз, когда одна функция вызывает другую, её состояние (локальные переменные, значения параметров) и точка, где такой вызов произошел, отправляются в стек.»

Здесь ещё одна, третья операция — запись состояния функции!

Раньше я не мог пробиться между двумя деревьями: есть операция повторного вызова функции (рекурсивный вызов) и есть операция вывода на печать. Вывод на печать не происходит, потому что до него дело не доходит, перед ней происходит рекурсивный вызов и функция начинается заново. А когда в конце срабатывает вывод на печать, то и функция должна заканчиваться, ведь дальше уже нет команд. И нет, как мне тогда казалось, здесь никаких незавершённых команд. Все команды начинаются и завершаются — проверка условия, рекурсивный вызов и вывод на печать.

А оказывается, что есть ещё одна операция — запись состояние функции. И выполняется она между этими рекурсивными вызовами. Функция запустилась, выполнена проверка условия, если true (значение меньше 11), то должен быть рекурсивный вызов. Но прежде чем он запустится, делается запись состояния функции, а именно — какие использовались переменные, какие у них значения и из какого места произошел рекурсивный вызов. Последнее или «точка вызова» определяет какая команда будет выполняться следующей. Теперь становится понятной последовательность команд.

Так и появляется незавершённая операция. Это не отдельная команда, а функция в целом. Функция запустилась, проверилось условие и здесь идет повторный, рекурсивный вызов, повторный запуск функции. Получается, что функция не завершена, потому что нужно было ещё напечатать! И так 10 раз функция запускается и прерывается, не завершается. И именно эти операции и помещаются в стек.

Дальше — дело техникии. Когда значение достигает 11, условие выдает false и запускается команда на печать. А за этой первой командой из стека достаются все остальные функции и выводят на печать свои значения. Функция состоит в целом из первой части проверки на условие и вывода на печать. Вывод на печать делается при любом раскладе проверки на условие: больше 11 или меньше — всё равно значение n будет выводиться на печать, потому что команда вывода на печать находится вне условия if. Поэтому все эти команды и исполняются после завершения рекурсии. Они должны были исполниться, но им мешал рекурсивный вызов.

Выводы по примеру 2

Оказывается есть такая операция — «запись состояния функции2 (перед рекурсионным вызовом). Незавершённой может быть не только отдельная команда, операция, а и функция в целом. Выполнилась одна команда функции, затем рекурсивный вызов и не выполнилась другая команда. В целом получается, что не завершена именно функция как набор команд.

Пример 3. Третье просветление. Хвостовая рекурсия

Когда я в самом начале статьи привёл этот пример, он казался простым:

Действительно, проверка на условие — печать и вызов заново. Но после двух предыдущих примеров я вдруг заметил одну деталь — здесь рекурсионный вызов находится вне тела условия if ! А это значит, что он должен выполняться независимо от результата проверки на условие! Значит он будет выполняться всегда! Это стало очередным потрясением и пришлось снова удариться в учебную рекурсию — гугл, форумы, вопросы. Решение ещё раз подсказал Тарас Диканев. Цитирую:

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

Другими словами: программа зависнет или умный компилятор её остановит. И ещё нагуглил, что такая рекурсия называется «хвостовой», так как она размещается в конце функции, в «хвосте». Таких рекурсионных вызовов следует избегать, чтобы не было всяких «глюков». У того же Тараса Диканева на странице нашёл ещё 2 правила:

  1. рекурсионный вызов должен быть именно в теле условия if, и
  2. рекурсионный вызов осуществляется с изменяемым параметром (должен передавать значение параметра, отличающееся от значения предыдущего вызова).


Всё это позволяет как раз избежать бесконечного вызова рекурсии.

Три случая применения рекурсии

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

  1. Для вывода последовательности чисел. Например, вывести на печать последовательность чисел из множества от 1 до 100.
  2. Для вывода суммы чисел множества. Например, нужно вывести на печать сумму всех чисел от 1 до 30.
  3. Для вывода произведения всех чисел того или иного множества. Например, вывести на печать перемноженные между собой числа от 1 до 50. Такая процедура имеет свое название — вычисление факториала.

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

Заключение

Такие вот были у меня злоключения с рекурсией и как их удалось побороть. Понятно, что это ещё не всё, есть ещё много вопросов, связанных с рекурсией. Но как начальный этап, как этап первого знакомства — это уже состоялось. Из своего ученического опыта по данной теме предложил бы преподавателям GeekBrains использовать пример №1 для первого знакомства с рекурсией. Он более понятный и на нём можно показать какие-то первые вещи: ту же незавершённость операций, стек и др.

Спасибо за внимание, желаю всем успехов!

В ходе изучения третьего урока по «Основам Программирования» попался пример на рекурсию. Нужно было вывести на экран последовательность чисел от 1 до 10. Здесь всё понятно: входящее значение проверяется на услови, и если «истина» — печатается число. Затем функция вызывает саму себя заново уже с новым значением (n+1).

В итоге получаем результат: 1 2 3 4 5 6 7 8 9 10

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

А результат получился таким: 11 10 9 8 7 6 5 4 3 2 1

Мало того, что напечаталась ещё и цифра 11, так вся последовательность вывелась в обратном порядке. Но самое главное — почему оно вообще печатается? Ведь при беглом взгляде на код представляется, что этого не должно быть! 10 раз оно проверялось на условие и функция запускала саму себя заново. По идее до команды вывода на печать дело не должно доходить, ведь она стоит после вызова. Только когда значение стало 11, тогда уже вызова нет, и доходит очередь до печати. И после того, как выполнена команда на печать, функция должна завершиться! Ведь после команды на печать уже нет других команд. Но реально печатается ещё 10 значений!

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

Почему я это делаю, зачем мне это надо?

Главная причина — в учебных материалах часто бывает, что теряешься и путаешься. И когда удаётся разобраться, то всегда появляется огромное желание с кем-то поделиться. Не зря ведь говорят, что когда рассказываешь, то сам ещё лучше усваиваешь. Ещё одна причина — на дворе веб 2.0! И содержание сайтов часто формируют сами пользователи. Яркий пример — Википедия. Ну и последняя — очень удобно, когда, например, в гугле можно найти разные варианты рассмотрения той или иной темы. Можно выбрать то, что тебе больше подходит. Пускай данная статья также выступает в качестве одного из вариантов объяснения рекурсии.

Кому это может быть интересно?

Конечно, вряд ли эта статья заинтересует опытных программистов. Данный материал я публикую в основном для таких же студентов-новичков. Прочитать эту статью будет особенно полезно тем, кто не имел ранее опыта программирования. От слова «совсем». Я предлагаю один из возможных вариантов изложения темы рекурсии. Или, если не полное изложение, то хотя бы изложение некоторых вопросов в этой теме. Которые ближе к начальной стадии понимания.

3 примера, 3 знания

По ходу разборок анализ вёлся на 3 примерах, которые помогли получить 3 новых сокровенных знания. В том смысле, что об этих знаниях как-то не много говорится в учебниках. Первые два примера упомянуты в начале, а просветление началось с третьего, найденного на просторах интернета в процессе гугления.

Пример 1. Первое просветление. Незаконченная операция и стек. Матрешка

Код примера приведен ниже и должен напечатать сумму чисел от 1 до 5:

Вставлено скриншотом, чтобы сохранить номера строк — на них удобно ссылаться по ходу. Также для удобства и наглядности эта картинка будет несколько раз дублироваться ниже. Мои дальнейшие комментарии будут на уровне ученического повторения пройденного материала и его применения к конкретной задаче. Поэтому ещё раз повторюсь, материал может быть интересен главным образом таким же ученикам, каким является автор этих строк. Его следует рассматривать в качестве одного из вариантов изложения темы рекурсии, точнее даже не всей темы рекурсии, а некоторых её общих, начальных вопросов.

Рассмотрим по шагам, что происходит в этой программе.

Шаг 1

В строке 16 происходит вызов функции pow. Происходит он через вызов другой команды — alert — всем нам известной команды вывода на печать. Запускается команда alert, а в качестве её значения в параметрах задаётся вызов функции pow. В параметрах вызова функции pow указывается значение 5. Можно ещё называть его стартовым, исходным значением. Таким образом, первая команда, которая исполняется — это команда alert с вызовом функции pow и передачей ей стартового параметра 5.

Шаг 2

На этом шаге запускается функция pow в строке 3:

Для начинающих программиистов есть интересное общее правило: команды исполняются последовательно, одна за одной по очереди. Здесь же получается, что вызов в 16-й строке, а сама команда запускается из 3-й. Ответ: на самом деле в 3-й строке функция как набор команд просто объявлена и описана, но здесь она ещё не запускается. А вот команда на запуск указана именно в 16-й строке. И второй момент — функция pow при запуске принимает значение 5 из вызова.

Шаг 3

Пока всё просто, значение проверяется на условие: если оно равно 1, то возвращается значение 1 в команду alert. Если значение не равно 1, т.е. результат проверки false, тогда осуществляется переход в else для выполнения размещенных там команд.

Шаг 4

Здесь начинается самое интересное. А именно — здесь есть команда:

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

А происходит то, что эта команда не завершается! Она должна была вернуть (return) в исходный вызов alert какое-то значение. Но проблема в том, что у неё нет этого значения или есть только часть этого значения. На первой итерации, как уже было сказано выше, это значение равно 5. Но к пятерке должна быть добавлена ещё какая-то цифра. И чтобы вычислить эту вторую цифру функция pow запущена заново. Функция запущена заново, а предыдущая команда осталась незавершённой. Это очень важный момент, который я вначале проскочил и скорее всего могут проскочить и другие начинающие программисты.

Вопрос: если команда не завершена, то что с ней происходит? Здесь появляется понятие стека. Само слово «стек» (от английского stack — стог, куча, множество) означает некоторый набор данных. В данном случае это набор незавершённых команд, поскольку у нас тут будет не одна команда, а несколько. Все они доходят до этого места и заворачиваются заново до тех пор, пока передаваемое значение не станет равно 1. Тогда, как было сказано ранее, произойдет return значения 1 в alert.

Особенностью хранения команд в стеке является то, что заходят они в одном порядке, а выходят в обратном. Другими словами, первый вошёл, последний вышел. И наоборот: последний вошёл, первый вышел. Для иллюстрации в этом случае часто используют пример со стопкой тарелок. Тарелки кладутся одна на другую (вход), а потом снимаются, начиная с верхней, которая была положена последней. Или пример для мачо — рожок магазина для автомата. Патроны вжимаются в него и выходят обратно первыми те, которые последние, сверху. Точно также и наши команды: они по очереди входят в стек и остаются там до поры до времени. В стеке они будут размещены так:

Самая первая по времени команда pow(5-1) будет помещена в самом низу, а самая последняя pow(2-1) окажется сверху. Именно этих вещей про незавершённость команды и про стек не было в первых темах, из-за чего и произошел затор. И тем более приятно, что удалось их проштудировать самому.

Шаг 5

Не менее интересно, что происходит потом, когда значение уменьшается до 1 и происходит передача 1 в alert. Смысл этой команды понятен, но что происходит после неё?

А происходит то, что функция не останавливается, не завершается, как можно было бы подумать и как действительно тогда мне представлялось. После этой команды начинают выполняться команды из стека, незавершённые команды. Они были запущены, они начали выполняться, но не могли закончить своё выполнение, поскольку их прерывал повторный запуск функции. И вот когда этого повторного запуска уже нет, тогда они и заканчивают своё выполнение. Здесь хорошую иллюстрацию подсказал Женя Жилинский с форума GeekBrains — записать исполнение этого кода матрёшкой, где следующий вызов является «вложенной функцией в предыдущую».

5 + pow(x-1) = 5 + ( 4 + pow(x-1) )= 5 +( 4 +( 3 + pow(x-1) ) ) = 5 +( 4 + ( 3 + (2 + pow(x-1) ) ) ) = 5 + (4 +( 3 +( 2 + 1) ) )

Сначала пружина, можно сказать, сжимается, 5 + (х-1), затем 5 + (4+(х-1)) и т.д., пока «х» не станет числом. И тогда получается простая арифметическая формула,

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

Выводы по примеру 1

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

И ещё один вывод, больше уже учебного плана: этот пример хорошо использовать на первых порах знакомства с рекурсией именно для знакомства с понятием «стек незавершенных операций».

Пример 2. Второе просветление. Запись состояния функции и незаконченность целостной функции, а не отдельной команды

Как уже было сказано ранее, эта программа выводит на экран последовательность чисел от 11 до 1.

Мастер Йода рекомендует:  Появилась новая малварь для Android, которая не атакует смартфоны в России

Конструкция кода здесь немного похожа на предыдущий пример, но есть и существенные отличия. Вызов функции делается примерно также из строки после описания самой функции. Но сам вызов прямой, без другой функции (в предыдущем примере там была функция alert). Вызов функции как таковой — Print10 с передачей стартового параметра 1. Функция вывода на печать здесь тоже есть, но она представлена уже другой командой — document.write — и помещена уже в тело самой функции. Условие — не проверка на равенство единице, а проверка на то, что параметр функции должен быть меньше 11.

Общий смысл выполнения кода такой: входной параметр проверяется на условие. Если число меньше 11, то функция запускается заново и к входящему параметру добавляется 1. Когда параметр доходит до значения 11, то повторного вызова функции не происходит, а значит выполняется команда вывода на печать. Самое главное — понять, что именно выводится на печать. Засада случилась именно по этому вопросу, поскольку мне представлялось, что если параметр доходит до 11, то происходит вывод на печать этого числа и всё! Ведь дальше после команды вывода на печать уже больше нет никаких команд, значит ничего больше и не должно происходить. Программа закончена?!

Но оказывается нет! По факту она печатает еще 10 значений в нисходящем порядке. Интуитивно понимаешь, что это связано с предыдущими проверками условия, но почему это попадает на печать? Оказывается, здесь опять есть «стек» и есть незавершенные операции. Но где они, эти незавершенные операции? Если сравнивать этот пример с предыдущим, то в предыдущим довольно чётко видна незавершённая операция, это команда:

Необходимо вернуть «х», который равен определённому значению, например, 5 (или 4, или 3 и т.д.), плюс вторую часть уравнения, которую ещё нужно вычислить — для чего и запускается функция заново. Мы не можем посчитать сумму, потому что нет второй части уравнения. Именно поэтому данная операция незавершённая. Но где незавершённая операция во втором примере? Ведь здесь нет операции сложения, есть только команда повторного вызова функции:

Этот вопрос загнал меня в тупик на несколько дней. Мне показалось, что решение связано с синтаксисом кода. Куда относится команда печати — в else или вообще вне условия if? Вспомнилось правило, что условие if может быть неполным, без else. И второй момент — если в теле условия if один оператор, одна команда, то можно фигурные скобки не ставить. Таким образом, структура функции здесь выглядит так, если её расписать полностью:

Условие if в данном случае неполное, в нём нет второй части else, или она пустая. На форуме GeekBrains обратили внимание на то, что за пустой else могут уволить с работы! А поскольку я ещё не работаю программистом, то в данном случае могу себе позволить рискнуть. И далее, команда document.write к результатам проверки условия отношения не имеет. Отсюда важное следствие — команда вывода на печать будет выполняться всегда, независимо от результатов проверки условия if !

Всё это немного прояснило ситуацию, но решения не принесло. Всё выглядело так — 10 раз проверялось условие и функция запускалась заново, после чего печаталось значение 11 и на этом программа должна была завершиться. В упор не видно было, где здесь незавершённая команда — все команды отрабатывают, все завершаются. В результате долгого гугления решение нашлось на стороннем ресурсе — на сайте Тараса Диканева. У него есть страница, специально посвящённая теме рекурсии. Но готового ответа там нет, его подсказал сам автор сайта в индивидуальном общении. А именно:

«Каждый раз, когда одна функция вызывает другую, её состояние (локальные переменные, значения параметров) и точка, где такой вызов произошел, отправляются в стек.»

Здесь ещё одна, третья операция — запись состояния функции!

Раньше я не мог пробиться между двумя деревьями: есть операция повторного вызова функции (рекурсивный вызов) и есть операция вывода на печать. Вывод на печать не происходит, потому что до него дело не доходит, перед ней происходит рекурсивный вызов и функция начинается заново. А когда в конце срабатывает вывод на печать, то и функция должна заканчиваться, ведь дальше уже нет команд. И нет, как мне тогда казалось, здесь никаких незавершённых команд. Все команды начинаются и завершаются — проверка условия, рекурсивный вызов и вывод на печать.

А оказывается, что есть ещё одна операция — запись состояние функции. И выполняется она между этими рекурсивными вызовами. Функция запустилась, выполнена проверка условия, если true (значение меньше 11), то должен быть рекурсивный вызов. Но прежде чем он запустится, делается запись состояния функции, а именно — какие использовались переменные, какие у них значения и из какого места произошел рекурсивный вызов. Последнее или «точка вызова» определяет какая команда будет выполняться следующей. Теперь становится понятной последовательность команд.


Так и появляется незавершённая операция. Это не отдельная команда, а функция в целом. Функция запустилась, проверилось условие и здесь идет повторный, рекурсивный вызов, повторный запуск функции. Получается, что функция не завершена, потому что нужно было ещё напечатать! И так 10 раз функция запускается и прерывается, не завершается. И именно эти операции и помещаются в стек.

Дальше — дело техникии. Когда значение достигает 11, условие выдает false и запускается команда на печать. А за этой первой командой из стека достаются все остальные функции и выводят на печать свои значения. Функция состоит в целом из первой части проверки на условие и вывода на печать. Вывод на печать делается при любом раскладе проверки на условие: больше 11 или меньше — всё равно значение n будет выводиться на печать, потому что команда вывода на печать находится вне условия if. Поэтому все эти команды и исполняются после завершения рекурсии. Они должны были исполниться, но им мешал рекурсивный вызов.

Выводы по примеру 2

Оказывается есть такая операция — «запись состояния функции2 (перед рекурсионным вызовом). Незавершённой может быть не только отдельная команда, операция, а и функция в целом. Выполнилась одна команда функции, затем рекурсивный вызов и не выполнилась другая команда. В целом получается, что не завершена именно функция как набор команд.

Пример 3. Третье просветление. Хвостовая рекурсия

Когда я в самом начале статьи привёл этот пример, он казался простым:

Действительно, проверка на условие — печать и вызов заново. Но после двух предыдущих примеров я вдруг заметил одну деталь — здесь рекурсионный вызов находится вне тела условия if ! А это значит, что он должен выполняться независимо от результата проверки на условие! Значит он будет выполняться всегда! Это стало очередным потрясением и пришлось снова удариться в учебную рекурсию — гугл, форумы, вопросы. Решение ещё раз подсказал Тарас Диканев. Цитирую:

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

Другими словами: программа зависнет или умный компилятор её остановит. И ещё нагуглил, что такая рекурсия называется «хвостовой», так как она размещается в конце функции, в «хвосте». Таких рекурсионных вызовов следует избегать, чтобы не было всяких «глюков». У того же Тараса Диканева на странице нашёл ещё 2 правила:

  1. рекурсионный вызов должен быть именно в теле условия if, и
  2. рекурсионный вызов осуществляется с изменяемым параметром (должен передавать значение параметра, отличающееся от значения предыдущего вызова).

Всё это позволяет как раз избежать бесконечного вызова рекурсии.

Три случая применения рекурсии

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

  1. Для вывода последовательности чисел. Например, вывести на печать последовательность чисел из множества от 1 до 100.
  2. Для вывода суммы чисел множества. Например, нужно вывести на печать сумму всех чисел от 1 до 30.
  3. Для вывода произведения всех чисел того или иного множества. Например, вывести на печать перемноженные между собой числа от 1 до 50. Такая процедура имеет свое название — вычисление факториала.

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

Заключение

Такие вот были у меня злоключения с рекурсией и как их удалось побороть. Понятно, что это ещё не всё, есть ещё много вопросов, связанных с рекурсией. Но как начальный этап, как этап первого знакомства — это уже состоялось. Из своего ученического опыта по данной теме предложил бы преподавателям GeekBrains использовать пример №1 для первого знакомства с рекурсией. Он более понятный и на нём можно показать какие-то первые вещи: ту же незавершённость операций, стек и др.

Рекурсивное программирование

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

Я думаю, что тем, кто пытается постигнуть концепцию рекурсии, следует сначала понять, что рекурсия — это больше, чем просто практика в программировании. Это философия решения проблем, которые можно решать частями, не трогая основную часть проблемы, при этом, проблема упрощается или становится меньше. Рекурсия применима не только в программировании, но и в простых повседневных задачах. Например, возьмите меня, пишущего эту статью: допустим, я хочу написать около 1000 слов, и ставлю цель писать 100 слов каждый раз, когда сажусь за работу. Получается, что в первый раз я напишу 100 слов и оставляю 900 слов на потом. В следующий раз я напишу ещё 100 слов, а оставлю 800. Я буду продолжать, пока не останется 0 слов. Каждый раз, я частично решаю проблему, а оставшаяся часть проблемы уменьшается.

Работу над статьей можно представить в виде такого кода:

Также, этот алгоритм можно реализовать итеративно:

Если рассматривать вызов функции write_words(1000) в любой из этих реализаций, вы обнаружите, одинаковое поведение. На самом деле, каждую задачу, которую можно решить с помощью рекурсии, мы также можем решить с помощью итерации (циклы for и while ). Так почему же стоит использовать именно рекурсию?

Почему рекурсия?

Хотите верьте, хотите нет, но с помощью рекурсии некоторые проблемы решить легче, чем с помощью итерации. Иногда рекурсия более эффективна, иногда более читаема, а иногда просто быстрее реализуется. Некоторые структуры данных, такие как деревья ― хорошо подходят для рекурсивных алгоритмов. Существуют языки программирования, в которых вообще нет понятия цикла — это чисто функциональные языки, такие как Haskell, они полностью зависят от рекурсии для итеративного решения задач. Я хочу сказать, что программисту не обязательно понимать рекурсию, но хороший программист, просто обязан в этом разбираться. Более того, понимание рекурсии сделает вас отличным «решателем» проблем, не только в программировании!

Суть рекурсии

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

Предположим, у нас есть фактические данные определённого типа, назовём их dₒ. Идея рекурсии состоит в том, чтобы предположить, что мы уже решили задачу или вычислили желаемую функцию f для всех форм этого типа данных. Каждая из этих форм проще общей сложности dₒ, которую нам нужно определить. Следовательно, если мы можем найти способ выражения f(dₒ), исходя из одной или нескольких частей f(d), где все эти d проще, чем dₒ, значит мы нашли решение для f(dₒ). Мы повторяем этот процесс, и рассчитываем, что в какой-то момент оставшиеся f(d) станут настолько простыми, что мы сможем легко реализовать фиксированное, окончательное решение для них. В итоге, решением исходной задачи станет поэтапное решение более простых задач.

В приведённом выше примере (про написание статьи), данными является текст, содержащийся в документе, который я должен написать, а степень сложности — это длина документа. Это немного надуманный пример, но если предположить, что я уже решил задачу f(900) (написать 900 слов), то все, что мне нужно сделать, чтобы решить f(1000), ― это написать 100 слов и выполнить решение для 900 слов, f(900).

Давайте рассмотрим пример получше: с числами Фибоначчи, где 1-е число равно 0, второе равно 1, а nᵗʰ число равно сумме двух предыдущих. Предположим, у нас есть функция Фибоначчи, которая сообщает нам nᵗʰ число:

Как будет выглядеть выполнение такой функции? Возьмём для примера fib(4) :

В процессе рекурсивного решения задачи полезно повторять мантру: «Притворяйся, пока это не станет правдой», то есть делай вид, что ты уже решил более простую часть задачи. Затем попытайся уменьшить большую часть задачи, чтобы использовать решение упрощённой части. Подходящая для рекурсии задача, на самом деле должна иметь небольшое количество простых частей, которые нужно решить явно. Другими словами, метод сокращения до более простой задачи может быть использован для решения любого другого случая. Это можно проиллюстрировать на примере чисел Фибоначчи, где для определения fib(n) мы действуем, как будто мы уже рассчитали fib(n-1) и fib(n-2). В тоже время мы рассчитываем, что эти каскады и упрощения приведут к более простым случаям, пока мы не достигнем fib(0) и fib(1) , которые имеют фиксированные и простые решения.

Рекурсивная стратегия

Рекурсивный подход — дело тонкое, и зависит от того, какую проблему вы пытаетесь решить. Тем не менее, есть некоторая общая стратегия, которая поможет вам двигаться в правильном направлении. Эта стратегия состоит из трёх шагов:

  1. Упорядочить данные
  2. Решить малую часть проблемы
  3. Решить большую часть проблемы

Как я уже говорил, я думаю, что для обучения полезно приводить пример, но помните, что рекурсивный подход зависит от конкретной задачи. Поэтому старайтесь сосредоточиться на общих принципах. Мы рассмотрим простой пример с реверсом строки. Мы напишем функцию reverse, которая будет работать так: reverse(‘Hello world’) = ‘dlrow olleH’ . Я рекомендую вернуться назад и посмотреть, как эти шаги применяются к функции Фибоначчи, а затем попробовать применить их на других примерах (в интернете можно найти много упражнений).

Упорядочивание данных

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

После того, как мы упорядочили данные, нам нужно подумать об этом, как о чём-то, что мы можем сократить. На самом деле, мы можем записать наш порядок в виде последовательности:

0, 1, 2, …, n для чисел (т.е. для int данных d, степень(d) = d)

[], [■], [■, ■], …, [■, … , ■] для списков (len = 0, len = 1, …, len = n и т.д. для списка d, степень(d) = len(d))

Двигаясь справа налево, мы идём от общего («большая часть задачи») случая, к базовым («маленьким частям») случаям. В нашем примере с функцией reverse мы работаем со строкой, и можем взять длину строки за основу, для упорядочивания или определения степени сложности задачи.

Решаем малую часть проблемы

Как правило это самая лёгкая часть. После того, как мы определились с порядком, мы должны выделить в нём самые маленькие элементы, и решить, как мы будем обрабатывать их. Обычно, можно найти очевидное решение: в случае reverse(s) , как только мы дойдём до len(s) == 0 , имея при этом reverse(») , это будет знаком, что мы нашли ответ, потому что реверс пустой строки ничего не даст, т.е. нам вернётся пустая строка, так как у нас нет символов, которые можно перемещать. Если мы знаем решение для базового случая, и мы знаем порядок, то для нас, степень сложности решения общего случая, уменьшается в зависимости от степени сложности данных, которыми мы оперируем, приближаясь к базовым случаям. Мы должны быть внимательны, чтобы не пропустить ни одного базового случая: они и называются базовыми, потому что образуют основу порядка. Пропуск маленького шага считается распространённой ошибкой в сложных рекурсивных задачах, и приводит к бессмысленным данным или ошибкам.

Переходим к общим случаям

На этом этапе мы обрабатываем данные двигаясь вправо, то есть в сторону высокой степени. Как правило, мы рассматриваем данные произвольной степени, и ищем способ решения проблемы, упрощая её до выражения, представляющего ту же проблему, но в меньшей степени. Например, в случае с числами Фибоначчи мы начали с произвольного значения n и упростили fib(n) до fib(n-1) + fib(n-2) , что является выражением, содержащим два экземпляра той же задачи, но в меньшей степени (n-1 и n-2, соответственно).

Возвращаясь к алгоритму reverse , мы можем рассмотреть произвольную строку с длинной n, и предположить, что наша reverse функция работает для всех строк с длинной меньше n. Как мы можем использовать это, решая задачу для строки с длинной n? Мы могли бы сделать реверс строки, переместив всё, кроме последнего символа, а затем вставить этот последний символ в начало. В коде:

где string[-1] соответствует последнему символу, а string[:-1] соответствует строке без последнего символа (это питонизм). Последний член функции reverse(string[:-1]) , и является нашей исходной задачей, но он оперирует со строкой длины n-1. Таким образом, мы выразили нашу исходную задачу в решении той же задачи, но в уменьшенной степени.

Применив это решение к функции reverse , мы получаем следующее:

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

Напутствие

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

Иногда в более сложных рекурсивных задачах, шаги 2 и 3, о которых мы говорили, принимают форму более циклического процесса. Если вы не можете быстро найти общее решение проблемы, попробуйте решить рекурсивные (большие) случаи и базовые (маленькие) случаи, которые сможете найти, а затем посмотрите, как в результате разделились разные части данных. Это должно выявить любые недостающие базовые и рекурсивные случаи или те, которые плохо взаимодействуют друг с другом и нуждаются в переосмыслении.

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

Рекурсия

Рекурсия — состоит в определении, описании, изображении какого-либо объекта или процесса внутри самого этого объекта или процесса. Это ситуация, когда объект является частью самого себя.

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

Процедура func() вызывается с параметром 3. В ней содержится вызов процедуры func() с параметром 2. Предыдущий вызов еще не завершился, поэтому создается еще одна процедура и до окончания ее работы func(3) свою работу приостанавливает. Процесс вызова заканчивается, когда параметр равен 0. В этот момент одновременно выполняются 4 экземпляра процедуры.

Количество одновременно выполняемых процедур называют глубиной рекурсии .

Последняя вызванная процедура func(0) выведет число 0 и закончит свою работу. После этого управление возвращается к процедуре, которая ее вызвала: func(1) и выводится число 1. И так далее пока не завершатся все процедуры.

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

Сложная рекурсия

Возможна чуть более сложная схема: функция A вызывает функцию B, а та в свою очередь вызывает A. Это называется сложной рекурсией . При этом оказывается, что описываемая первой процедура должна вызывать еще не описанную. Чтобы это было возможно, требуется использовать описание функции B до ее использования.
Пример : вычислить значение выражения

Префиксная и постфиксная форма записи

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

Добавить комментарий