Глава 7 рекурсия


Содержание

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

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

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

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

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

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

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

В качестве первого примера напишем функцию 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).

лабы по информатике, егэ

лабораторные работы и задачи по программированию и информатике, егэ по информатике

Pascal: Занятие № 14. Рекурсия в Паскале

Рекурсия

Если в теле функции встречается вызов самой этой функции, то это и есть рекурсия.

Рекурсивностью в Паскале могут обладать как функции, так и процедуры.

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

Рассмотрим простой пример использования рекурсивной процедуры:

procedure row(n:integer); begin if n >=1 then begin write (n, ‘ ‘); row(n-1) end; end; begin row(10); end.

Теперь рассмотрим более сложный пример использования рекурсии в Паскаль.

Например: при переданном функции числе 3078 , должно в итоге вернуть 8703
Использовать операции div и mod.

procedure reverse (n: integer); begin write (n mod 10); if (n div 10) <> 0 then reverse(n div 10) end; begin writeln; reverse(3078); end.

Подсказка:
2!=2*1=2
3!=3*2*1=6
Выводим формулу a!=a*((a-1)!)

var x: integer; function fact (a: integer): integer; begin if (a sumTo(n) , которая для данного n вычисляет сумму чисел от 1 до n , например:
sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
.

var x,y: integer; function stepen (a,b: integer):integer; var . begin . end; begin writeln(‘число?’); readln(x); writeln(‘степень?’); readln(y); writeln(stepen(x,y)); end.

Для чисел 3430 и 1365:

остаток от деления 3430 на 1365 3430 mod 1365 = 700
остаток не равен нулю, повторим то же действие, подставив вместо первого числа второе, а вместо второго – остаток 1365 mod 700 = 665
остаток также не нуль, поэтому еще одно деление 700 mod 665 = 35
остаток также не нуль, поэтому еще одно деление 665 mod 35 = 0
остаток нуль НОД равен 35

procedure fib (i,n: integer); begin writeln (i+n,’ ‘); if . then fib(. ) end; begin fib(0,1); end.

Потренируйтесь в решении задач по теме, щелкнув по пиктограмме:

Рекурсия

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

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

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

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

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

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

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

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

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


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

Чтобы понять, что такое рекурсия, нужно понять, что такое рекурсия.

Дубликаты не найдены

Чтобы понять что такое рекурсия нужно понять что такое рекурсия

Вообще рекурсия это не всегда бесконечное вхождение процесса самого в себя. На рисунке как раз изображена бесконечная рекурсия. Такой вид рекурсии в принципе самый распространённый и она заканчивается вместе с потоком информации. Я программист и житейское мне чуждо, поэтом не могу объяснить это по человечески. Если по программерски, то допустим что есть некий многомерный массив и он содержит строки и так же массивы, содержащие в себе строки и массивы. Есть некая функция, которая строит двумерное дерево для этого го массива и на каждом попадании массива в ячейке делает разветвление для создания, грубо говоря, дерева на дереве. Вложенной иерархической структуры. Так вот есть функция для обработки массива и если она встречает строку, то рисует листик, а если массив, то запускает саму себя чтобы узнать где находится второй «ближайший» листик. Следующую конечную ветку.

Лекция 4 : Рекурсия

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

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

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

Запишем эту идею:

/* предком является родитель */

/* предком является родитель предка */

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

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

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

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

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

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

1!=1 /* факториал единицы равен единице */

N!=(N-1)!*N /* для того, чтобы вычислить факториал

некоторого числа, нужно вычислить

факториал числа на единицу меньшего

и умножить его на исходное число */

Попробуем записать реализацию предиката, эквивалентную математическому определению предиката:

fact(1,1). /* факториал единицы равен единице */

fact(N1,F1), /* F1 равен факториалу числа

на единицу меньшего исходного

F=F1*N. /* факториал исходного числа равен

произведению F1 на само число */

К сожалению, при попытке вычислить факториал произвольного натурального числа с помощью описанного выше предиката fact произойдет переполнение стека («Stack overflow»). Попробуем разобраться, в чем причина. Рассмотрим, например, что будет происходить, если мы попытаемся вычислить факториал трех.

Соответствующий вопрос можно записать следующим образом:

Пролог-система попытается унифицировать цель с заголовком первого предложения (fact(1,1)). Ей это не удастся, поскольку число три не равно единице. При унификации цели с заголовком второго предложения (fact(N,F)) переменная N конкретизируется числом три, а переменная X связывается с переменной F. После этого происходит попытка выполнить подцели, расположенные в теле правила слева направо. Сначала переменная N1 означивается числом на единицу меньшим, чем значение переменной N, то есть двойкой. Срабатывание следующей подцели (fact(N1,F1)) приводит к рекурсивному вызову предиката, вычисляющего факториал, со значением переменной N1, равным двум.

Так же, как и в случае, когда первый аргумент был равен трем, унификации с головой первого предложения не происходит (единица не равна двум). Сопоставление с головой второго правила происходит успешно. Дальше все происходит почти так же, как для значения переменной N, равного трем. Вычисляется новое значение N1, равное двум без единицы, то есть единице. Пролог снова пытается вычислить подцель fact(N1,F1) (правда, со значением переменной N1, равным единице).

На этот раз происходит сопоставление цели (fact(1,F1)) с заголовком первого предложения, при этом переменная F1 конкретизируется единицей. Пролог-системе наконец-то удалось вычислить вторую подцель второго правила, и она переходит к вычислению третьей подцели (F=F1*N). Переменная N была равна двум, переменная F1 — единице, произведение двух и единицы равно двум и, значит, переменная F конкретизируется двойкой.

Начинается обратный ход рекурсии. После того, как был вычислен факториал двойки, Пролог-система готова вычислить факториал тройки. Для этого нужно умножить факториал двух на три. Переменная F будет конкретизирована числом шесть. Мы получили ответ на вопрос о факториале трех.

Однако вычисления на этом не заканчиваются. Пролог-система обнаруживает, что цель fact(1,F1) может быть сопоставлена не только с заголовком первого предложения, но и с заголовком правила (fact(N,F)). Переменная N конкретизируется единицей, а переменная F1 связывается с переменной F. После этого переменная N1 означивается числом на единицу меньшим, чем значение переменной N, то есть нулем. Пролог-система пытается вычислить цель fact(0,F1). С заголовком первого предложения (fact(1,1)) сопоставить эту цель не удается, поскольку ноль не равен единице. Зато с заголовком второго предложения (fact(N,F)) цель успешно унифицируется. Переменная N1 становится равна минус единице. После этого делается попытка вычислить цель fact(-1,F1). Потом fact(-2,F1), fact(-3,F1), fact(-4,F1), fact(-5,F1). .

Илон Маск рекомендует:  Шаблон музыкального сайта HTML, CSS, 6 страниц

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

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

Как можно исправить ошибку? У нас есть два варианта корректировки процедуры.

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

fact(1,1). /* факториал единицы равен единице */

N>1, /* убедимся, что число больше единицы */

fact(N1,F1), /* F1 равен факториалу числа,

на единицу меньшего исходного

F=F1*N. /* факториал исходного числа равен

произведению F1 на само число */

В этом случае, хотя и произойдет повторное согласование цели fact(1,F1) с заголовком правила, и переменная N будет конкретизирована единицей, а переменная F связана с переменной F1, первая подцель правила (N>1) будет ложной. На этом процесс оборвется. Попытки вычислять факториал на неположительных числах не произойдет, процедура будет работать именно так, как нам хотелось.

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

fact(1,1):-!. /* условие останова рекурсии */

fact(N1,F1), /* F1 равен факториалу числа,

на единицу меньшего исходного

F=F1*N. /* факториал исходного числа равен

произведению F1 на само число */

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

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

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

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


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

Вся процедура будет выглядеть следующим образом:

fact2(N,F,N,F):-!. /* останавливаем рекурсию, когда третий

аргумент равен первому*/

N2=N1+1, /* N2 — следующее натуральное число

F2=F1*N2, /* F2 — факториал N2 */

/* рекурсивный вызов с новым натуральным

числом N2 и соответствующим ему

посчитанным факториалом F2 */

Остановить рекурсию можно, воспользовавшись отсечением в базисе рекурсии, как это было сделано выше, или добавив в начало второго предложения сравнение N1 с N.

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

fact2(N,F,1,1). /* вызываем предикат с уже

Пример. В предыдущей лекции мы записали аналог императивного ветвления, воспользовавшись отсечением. Теперь напишем, используя рекурсию и отсечение, реализацию цикла с предусловием. Обычно этот цикл выглядит примерно так: while do P. Это соответствует текстовому описанию «пока имеет место , выполнять P». На Прологе подобную конструкцию можно записать следующим образом:

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

Базисов рекурсии в данном случае два. Первый будет утверждать, что первое число Фибоначчи равно единице. Второй базис — аналогичное утверждение про второе число Фибоначчи. Шаг рекурсии также будет необычным, поскольку будет опираться при вычислении следующего числа Фибоначчи не только на предшествующее ему число, но и на предшествующее предыдущему числу. В нем будет сформулировано, что для вычисления числа Фибоначчи с номером N сначала нужно вычислить и сложить числа Фибоначчи с номерами N-1 и N-2.

Записать эти рассуждения можно так:

fib(1,1):-!. /* первое число Фибоначчи равно единице */

fib(2,1):-!. /* второе число Фибоначчи равно единице */

N1=N-1, fib(N1,F1), /* F1 это N-1-е число

N2=N-2, fib(N2,F2), /* F2 это N-2-е число

F=F1+F2. /* N-е число Фибоначчи равно сумме

N-1-го и N-2-го чисел Фибоначчи */

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

Вместо этих двух отсечений от зацикливания можно избавиться путем добавления в начало правила, реализующего шаг рекурсии, проверки значения, находящегося в первом параметре предиката (N>2). Это условие в явном виде указывает, что рекурсивное правило применяется для вычисления чисел Фибоначчи, начиная с третьего.

Но надо сказать, что хотя наше решение получилось ясным и прозрачным, довольно точно соответствующим определению чисел Фибоначчи, оно, тем не менее, весьма неэффективное. При вычислении N-1-го числа Фибоначчи F1 вычисляются все предыдущие числа Фибоначчи, в частности, N-2-е число Фибоначчи F2. После этого заново начинает вычисляться N-2-е число Фибоначчи, которое уже было вычислено. Мало того, опять вычисляются все предыдущие числа Фибоначчи. Получается, что для вычисления числа Фибоначчи используется количество рекурсивных вызовов предиката fib, равное искомому числу Фиббоначи.

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

Вот как будет выглядеть этот предикат:

fib_fast(1,1,1):-!. /* первые два числа Фибоначчи равны

/* FN_1 это N-1-е число

Фибоначчи, FN это

N-е число Фибоначчи */

FN1=FN+FN_1. /* FN1 это N+1-е число Фибоначчи */

Несмотря на то, что предикат fib_fast находит, в отличие от предиката fib, не одно число Фибоначчи, а сразу два, он использует намного меньше стекового пространства и работает во много раз быстрее. Для вычисления числа Фибоначчи с номером N (а заодно и N+1-го числа Фибоначчи) необходимо всего лишь N рекурсивных вызовов предиката fib_fast.

Если нам не нужно следующее число Фибоначчи, можно сделать последним аргументом анонимную переменную или добавить описанный ниже двухаргументный предикат:

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

родитель(Предок,Потомок). /* предком является

предок2(Человек,Потомок), /* предком является

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

С оригинальным предикатом предок этого не происходило, потому что в его втором правиле первой подцелью стоял вызов подцели родитель. В результате выполнения этой подцели переменная Человек получала в качестве значения имя какого-то человека. Поэтому в момент вызова второй подцели предок(Человек,Потомок) переменная Человек была уже связанной. В новой же версии предиката второе правило начинается с вызова подцели предок2(Человек,Потомок), причем переменная Человек в ней свободна. После того, как будут исчерпаны все альтернативы для означивания свободных переменных через первое предложение процедуры, подцель будет унифицироваться с заголовком второго предложения. Свободная переменная Человек будет связана с переменной Предок, а переменная Потомок подцели — с переменной Потомок заголовка правила. При попытке выполнить первую подцель правила все повторится. Этот процесс будет продолжаться до тех пор, пока не будет исчерпано все свободное пространство стека.

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

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Для студентов недели бывают четные, нечетные и зачетные. 9438 — | 7438 — или читать все.

7 . Алгоритмы

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

— алгоритмы, в которых поиск решения сводится к формулировке одной или нескольких задач меньшей размерности;

— алгоритмы, соблюдающие установленные для них соотношения (свойства, «законы», инварианты);

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

7 .1. Цикл, итерация, рекурсия

Рекурсивным называется способ построения объекта (понятия, системы, описание действия), в котором определение объекта включает аналогичные объекты (понятие, систему, действие) в виде составных частей.

Рекурсия в жизни, литературе, искусстве

Примеры рекурсии можно встретить в литературе, искусстве, фольклоре.

«У попа была собака, он ее любил.

Она съела кусок мяса, он ее убил.

Камнем придавил, и на камне написал:

Я хочу Вам написать, что я хочу Вам написать, что я хочу Вам написать . . .

«Я оглянулся посмотреть,

не оглянулась ли она,


чтоб посмотреть, не оглянулся ли я. »

В тамбуре, пуская дым в окошко, Монахов на некоторое время обрел пространство: мусорный ящик, огнетушитель, декларация какая-то под стеклом, дверь в туалет, плевок – все на месте. Давно пора было закурить… подчеркнуто выпустил дым – отлегло. Что это все на него находит? Благожелательно приласкал взглядом огнетушитель: на месте, друг! Не действуешь. И то, что на огнетушителе была картинка, на которой человек, успев переодеться в комбинезон, правильно держал в руках точно такой же огнетушитель, на котором, в свою очередь, была картинка, на которой… это, с детства запавшее представление, тут же тысячу раз проигранное в мозгу, не было почему-то ему противно, наоборот: усмехнулся себе ласково, будто подмигнул прошлому… (Андрей Битов. “Вкус”).

Все образные примеры рекурсии подмечают главное ее свойство: некоторая часть системы воспроизводит самое себя. Здесь же отмечается особенность такого подхода: рекурсия не свойственна обыденному восприятию, безусловная рекурсия бесконечна и бессмысленна. Ограниченная рекурсия с определенным количеством уровней – парадоксальна и опасна. Например, рефлексия (от лат. reflexio – обращение назад) – самопознание, самонаблюдение, образное представление самого себя в третьем лице (см., например, «Поединок» А.Куприна).

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

В программировании таких примеров еще больше :

— определение любого конкретного оператора (условный, цикл, блок) в качестве составных частей включает произвольный оператор;

— рекурсивная структура данных — элемент структуры данных содержит один или несколько указателей на аналогичную структуру данных. Например, односвязный список можно определить как элемент списка, содержащий указатель NULL или указатель на аналогичный список;

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

Рекурсивные алгоритмы и функции и их свойства

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

//—— Циклический алгоритм вычисления факториала

for (int s=1; n!=0; n—) s *=n;

//—— Рекурсивный алгоритм вычисления факториала

return n * fact(n-1); >

Приведенный пример не демонстрирует каких-то особенных преимуществ линейной рекурсии. Тем не менее, линейная рекурсия элегантно смотрится на линейных структурах данных – односвязных списках.

//— Включение в односвязный с сохранением порядка – циклическая программа

// pr — указатель на предыдущий элемент списка

void InsSort(list *&ph, int v)

// перед переходом к следующему указатель на текущий

// запоминается как указатель на предыдущий

for ( p=ph,pr=NULL; p!=NULL && v>p->val; pr=p,p=p->next);

if ( pr == NULL ) // включение перед первым

else // иначе после предыдущего

< q ->next = p ; // следующий для нового = текущий

pr -> next = q ; >> // следующий для предыдущего = новый

//— Рекурсивное включение в односвязный список с сохранением порядка

void InsSort(list *&ph, int v)<

list * pp = new list ; // меньше следующего

ph == pp ; // ради присваивания по ссылке — рекурсия

else InsSort ( ph -> next , v ); // иначе – рекурсивный вызов для следующего

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

… if () F 1(); // Не более 2 рекурсивных вызовов

for ( int i =0; i m ; I ++) F 2(); // Рекурсивный вызов в цикле

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

vo > vo > vo > void F()

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

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

— при вызове функции в стек записывается точка возврата — адрес той части программы, где находится вызов функции;

— в начале тела функции в стеке резервируется место для локальных (автоматических) переменных.

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

Рекуррентные соотношения

// Вычисление чисел Фибоначчи итерационным методом

// F 2 – «позавчерашнее» значение ряда

// F 1 – «вчерашнее» значение ряда

// F 0 – «сегодняшнее» значение ряда

F 2= F 1, F 1= F 0; // при переходе к следующему шагу текущий становится

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

// Рекурсивное вычисление чисел Фибоначчи

if ( n >=1) return 1; // Для первых двух членов ряда — 1

return F ( n -1)+ F ( n -2); // Результат – сумма рекурсивно вычисленных значений

Diplom Consult.ru

Рекурсия имеет три основных преимущества:

— Она может выражать алгоритмы, которые нельзя удобно выразить ника-

ким другим образом.

— Она логически проще метода итерации.

— Она широко используется в обработке списков.

Рекурсия — хороший способ для описания задач, содержащих в себе под-


задачу такого же типа. Например, поиск в структуре дерева (дерево состав-

ляется из более мелких деревьев) и рекурсивная сортировка (сортировка

списков, разделение их на части, сортировка частей и составление их вмес-

Логически, рекурсивным алгоритмам присуща структура индуктивного ма-

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

факториала CH07EX03.PRO описывает бесконечное множество различных вычис-

лений с помощью всего лишь двух предложений. Кроме того, о правильности

каждого предложения можно судить независимо от другого.

Оптимизация хвостовой рекурсии

У рекурсии есть один большой недостаток — она съедает память. Всякий

раз, когда одна процедура вызывает другую, информация о выполнении вызы-

вающей процедуры должна быть сохранена для того, чтобы она (вызывающая

процедура) могла, после выполнения вызванной процедуры, возобновить вы-

полнение на том же месте, где остановилась. Это означает, что если проце-

дура вызывает себя 100 раз, то 100 различных состояний должно быть запи-

сано сразу. (Состояния решения сохраняются в стековой структуре (stack

frame).) Память IBM PC способна поместить от 3000 до 4000 стеков. А что

вы станете делать, если захотите повторить что-либо более 4000 раз?

Это исключает наличие специального случая, когда процедура может

вызвать себя без сохранения информации о своем состоянии. А, что если вы-

зывающая процедура не собирается возобновлять работу после выполнения

Предположим, что процедура вызывается последний раз, т.е. когда выз-

ванная процедура завершит работу, вызывающая процедура не должна больше

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

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

ванная процедура завершится, работа процессора должна идти в направлении,

указанном для вызывающей процедуры после ее выполнения.

Например, допустим, что процедура А вызывает процедуру В, а В вызы-

вает С в качестве своего последнего шага. Когда В вызывает С, В не должно

больше ничего делать. Поэтому, вместо того, чтобы сохранить для С текущее

состояние о процедуре В, вы можете переместить информацию из стека В (ко-

торый больше не нужен) в текущий стек С. Когда С закончит выполнение, она

будет считаться вызванной непосредственно процедурой А.

А сейчас предположим, что на последнем шаге выполнения процедура В,

вместо процедуры С вызывает себя. Рецепт говорит, что когда В вызывает В,

стек для вызывающей В должен быть заменен стеком для вызванной В. Это

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

и возвратом процессора к началу процедуры. Поэтому, для процедуры это оз-

начает лишь обновление управляющих переменных в цикле.

Эта операция называется оптимизацией хвостовой рекурсии или оптими-

Рекурсия

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

Идея рекурсивных процессов в том, что повторное рассмотрение области в конце концов проясняет ее. Оно пробивается через любые механизмы общения и заставляет человека посмотреть на то, что есть на самом деле.

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

Илон Маск рекомендует:  count - Посчитать количество элементов массива или количество свойств объекта

Рекурсивные техники состоят из одного указания или вопроса, или из нескольких указаний или вопросов. Если есть несколько указаний, они даются последовательно снова и снова.

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

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

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

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

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

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

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

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

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

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

«Расскажи мне о сексе»

«Что может быть интересным?»


«В чем ты добился успеха?»

«Подумай о взаимоотношениях»

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

«Расскажи мне о _____»

«Что ты думал о _____»

«Что произошло в связи с _____?»

«Чего ты не понимаешь в _____?»

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

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

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

В ходе изучения третьего урока по «Основам Программирования» попался пример на рекурсию. Нужно было вывести на экран последовательность чисел от 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.

Конструкция кода здесь немного похожа на предыдущий пример, но есть и существенные отличия. Вызов функции делается примерно также из строки после описания самой функции. Но сам вызов прямой, без другой функции (в предыдущем примере там была функция 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 или на другое число). И дополнительная операция — сложение или умножение всех чисел множества.

Илон Маск рекомендует:  Как в PowerPoint сделать автоматическую смену слайдов

Заключение

Такие вот были у меня злоключения с рекурсией и как их удалось побороть. Понятно, что это ещё не всё, есть ещё много вопросов, связанных с рекурсией. Но как начальный этап, как этап первого знакомства — это уже состоялось. Из своего ученического опыта по данной теме предложил бы преподавателям 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.

Конструкция кода здесь немного похожа на предыдущий пример, но есть и существенные отличия. Вызов функции делается примерно также из строки после описания самой функции. Но сам вызов прямой, без другой функции (в предыдущем примере там была функция 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 для первого знакомства с рекурсией. Он более понятный и на нём можно показать какие-то первые вещи: ту же незавершённость операций, стек и др.

PHP скрипты

Apache

PHP Скрипты

Для Дизайна Сайта

Партнеры

  • PHP для начинающих
  • Cимволы HTML
  • MySQL: Уроки, руководство
  • cPanel
  • Список кодировок

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

Например, попробуем написать функцию с помощью обычного цикла for, возвращающую факториал числа. Из курса математики известно, что он вычисляется следующим образом: n! =1*2. *(n-1 )*n. Причем 0!=1, а факториала отрицательных чисел не бывает (листинг 7.13).

Листинг 7.13. Функция нахождения факториала числа без рекурсии.

‹html›
‹head›
‹title›Функция нахождения факториала числа без рекурсии‹/title›
‹/head›
‹body›
‹?php
function factorial($num)
<
if ($num

Итак, задача решена, как говорится, «в лоб». В случае передачи отрицательных значений функция будет возвращать 0. Это реализуется с помощью первого оператора if. Далее если передано число 0, то возвращаем единицу. И наконец, в цикле for вычисляем факториал при любых других значениях.

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

n! = 1, если n=0
n! = n*(n-1)!, если n>0

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

Итак, вернемся к рассуждению о факториале. При решении задач с помощью рекурсии всегда надо иметь два типа утверждений: базисное и рекурсивное. В нашем случае базисным утверждением является n! = 1, если n = 0. Как вы, наверное, уже догадались, работая с рекурсивным утверждением, мы должны перейти к базисному и получить результат. Теперь попробуем реализовать все это на практике (листинг 7.14).

Листинг 7.14. Функция нахождения факториала числа с рекурсией

‹html›
‹head›
‹title›Функция нахождения факториала числа с рекурсией‹/title›
‹/head›
‹body›
‹?php
function factorial($num)
<
if ($num

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

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL