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

Знакомство с рекурсией и её особенностями.
31 октября 2016872722maxs mass41773339

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

alert(pow(5));

Шаг 2

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

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

Шаг 3

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

Шаг 4

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

return x + pow(x-1);

С одной стороны вроде понятно, что функция 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)) и т.д., пока "х" не станет числом. И тогда получается простая арифметическая формула,

5 + (4 +( 3 +( 2 + 1)))

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

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

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

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

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

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

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

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

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

return x + pow(x-1);

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

Print10(n+1);

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

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

 

Популярные статьи

Новые комментарии