Глава 9. Рекурсивное мышление

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

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

Пример первый. Факториал   

Факториал числа N – это произведение всех чисел от 1 до N. Отметим, что требование умножения на 1 вроде бы как бессмысленно, но это требование математического определения факториала, поэтому примем его как данное. Выражение выглядит так:

N! = 1*2*….*N

Это определение называется нерекурсивным. Математики еще говорят о рекуррентных определениях. Но далее, чтобы не путаться в терминологии оставим два рабочих термина: рекурсивное определение и нерекурсивное. Таким образом, данное определение нерекурсивное. Заметим, что его можно переписать так:

N! =1*2*…*(N-1)*N

Или что тоже самое:

N!=(N-1)!*N

А это уже рекурсивная запись, означающая, что для вычисления факториала от числа N необходимо вычислить факториал числа N-1 и умножить его на N. Рекурсивный спуск для факториала продолжается до тех пор, пока алгоритм не придет к задаче счета факториала от единицы, что и называется тривиальным случаем. Пока счет не дошел до тривиального случая, спуск продолжается. После счета тривиального случая: 1! = 1,  начинается подъем наверх с учетом уже посчитанных значений. А именно 2!=2*1!, затем 3! = 3*2!,  и т.д. Здесь факториалы справа от знака равенства уже посчитаны в предыдущем выражении.
Из сказанного следует общий вывод – рекурсивное решение строится на базе рекурсивного определения величины. Вот эта формула N!=(N-1)!*N и есть рекурсивное определение факториала. Необходимо также определение тривиального случая, обеспечивающего завершение спуска. В нашем случае это равенство: 1! =1

Обобщенное понимание рекурсии

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

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

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

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

Пример второй. Игра Ним 

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

Предварительное замечание. Как всегда, решение задачи необходимо начинать с уточнения условия. Цель нашего поиска – выигрышный  алгоритм. Разумеется, он не может быть выигрышным для обоих игроков. Действительно, пусть оба игрока знают этот алгоритм или арифметическое правило взятия  спичек. Ясно, что выиграть может только один игрок, но вот кто из них, первый или второй. Исследуем этот предварительный вопрос и таким образом уточним условие. 
Исчерпывающе и доказательно ответить на этот вопрос можно, только получив выигрышный алгоритм. Но как ни странно вполне убедительный ответ возможен и на базе общего суждения. Первый игрок, в своем первом ходе не ограничен действиями второго игрока, так как этот второй еще не вступил в игру. И если существует выигрышный алгоритм, то существует и первый выигрышный ход и он доступен первому игроку.

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

Определим тривиальную раскладку. Я опускаю промежуточные рассуждения, и без того анализ игры уже содержит много текста. Тривиальный случай: 1, 2, 3 (ход за вторым игроком). Проверить, что поражение второго игрока в такой раскладке неизбежно, не составляет большого труда. Что здесь сразу бросается в глаза. Сумма спичек двух малых кучках равна количеству спичек в большой. Более того, если вы поиграете, начиная с этой позиции, то не составит труда понять, что именно это арифметическое соотношение и есть причина гарантированного выигрыша.

И это уже не гипотеза, а правило. Далее все очень просто. Первый игрок должен делать ход, такой, чтобы новая раскладка удовлетворяла полученному арифметическому соотношению. Стартовая раскладка, как можно видеть, ему не удовлетворяет. Первый игрок может изменить раскладку (7, 5, 3) взяв спичку из третьей кучки создав раскладку (7, 5, 2). Если второй игрок сделает ход, в результате которого, раскладка не будет удовлетворять требуемому соотношению, то первый игрок сможет это соотношение восстановить. Если же второй игрок сам попробует сохранить соотношение, то он может сделать это единственным способом, создав раскладку (3, 5, 2) дав возможность для первого перейти одним ходом к тривиальному случаю (3, 1, 2) после чего второй очевидно проигрывает.

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

Инвариант рекурсивного процесса   

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

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

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

 Еще раз о программистской версии рекурсии

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

Пример третий. Числа Фиббоначи.

Ряд чисел с таким названием начинается с двух единиц и каждое последующее равно сумме двух предыдущих. То есть это следующий ряд: 1, 1, 2, 3, 5, 8, 13, 18, 31…..
Рекурсивное определение ряда выглядит так:

• A(1) = 1
• A(2) = 1
• A(n) = A(n-1) + A(n-2)

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

Ввести число N
Результат = Фиббоначи(N)

Здесь записано, что будет исполнена некая последовательность действий результатом которой станет число Фиббоначи с номером N. Осталось записать эту последовательность.

Процедура Фиббоначи
Входные данные: Число N
Если N=1 или N=2 тогда вернуть 1
Иначе вернуть Фиббоначи(N-1) + Фиббоначи(N-2)

Обратите внимание, здесь просто записано математическое определение чисел этого ряда. Осталось посмотреть, как это работает. Разберем пример счета числа с номером 5. На первом шаге вызывается процедура Фиббоначи(5). Будем для краткости вызов функции обозначать символом F. Итак, требуется посчитать F(5). Это случай не тривиальный. Поэтому функция приостанавливает свою работу до получения результатов от F(4) и F(3), так как согласно рекурсивной формуле F(5) = F(4) + F(3). Здесь тривиальных случаев нет. Поэтому продолжаем спуск: F(5) = F(3) + F(2) + F(2) + F(1), Появилось три тривиальных случая: F(5) = F(3) + 1 + 1 + 1. Остался один нетривиальный, распадающийся еще на два F(5) = F(2) + F(1) + 1 + 1 + 1 = 5
Заметим, что даже при небольшом значении аргумента, мы получим довольно значительный объем вычислений, так как функция F быстро ветвится. Но в случае передачи процесса вычислительной машине, объем работы не критичен. В этом случае существенно значим объем работы программиста, а он сводится к записи правил рекурсивного счета. Разворачивание процесса полностью уходит из поля зрения программиста. Заметим, что ни один программист, конечно, не будет строить этот ряд чисел рекурсивной процедурой, но пример полезен как иллюстрация метода.

Пример четвертый. Задача Дейкстры

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

1. F(1) = 1
2. F(2n) = F(n)
3. F(2n + 1) = F(n) + F(n + 1)

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

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

Ввести число N
Результат = Дейкстра(N)

Рекурсивная функция выглядит лишь немного сложнее

Если N =1 То Вернуть 1
Иначе
Если N четное то вернуть Дейстра(N DIV 2)
Иначе вернуть Дейкстра(N DIV 2) + Дейкстра((N DIV 2) + 1)

Операция DIV здесь обозначает целочисленное деление с округлением до меньшего целого. Для понимания вычислительного процесса приведем небольшой счетный пример. Функцию Дейкстры обозначим для краткости через F. Посчитаем ее значение от аргумента 7. Это нечетное число, поэтому F(7) = F(3) + F(4) функция, записанная слева, ждет значений от функций составляющих сумму. Первая из них нечетная, вторая четная, поэтому: F(7) = (F(2) + F(1)) + F(2). Сейчас справа записано три функции, одна из которых тривиальная, две других четны, поэтому F(7) = (F(1) + F(1)) + F(1) = 3F(1) = 3. Аргумент примера не велик, но думаю понятно, большой аргумент будет представлять существенную проблему для ручного счета.
Два рассмотренных выше примера демонстрируют мощь рекурсии в ситуации необходимости организации ветвящегося вычислительного процесса, предназначенного для исполнителя умеющего быстро выполнять вычислительные операции и обладающего для этого достаточно большой памятью.

Задачи сортировки

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

Пример пятый. Быстрая сортировка

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

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

Что значит отсортировать в порядке возрастания. Есть общее определение этого состояния, которое можно назвать тавтологией. Массив, отсортированный в порядке возрастания, это такой массив в котором больший элемент расположен правее любого меньшего. Такое определение не информативно, поэтому все алгоритмы сортировки, а их довольно много, опираются на частные определения, использующие какие-то локальные свойства отсортированного массива.
Например, самый простой алгоритм сортировки «Пузырьком» полагает, что массив отсортирован, если в любой паре рядом стоящих элементов первый меньше второго. Очевидно, что если в массиве нет неправильных пар, что он отсортирован. Из этого определения следует и идея «Пузырька» – необходимо искать неправильные пары и менять в них первый и второй элементы местами. Процесс завершается тогда, когда выясняется, что неправильных пар больше нет.

Такое функциональное определение есть и для быстрой сортировки. Массив считается отсортированным, если отсортирован любой его подмассив. Пример: 1, 6, 8, 9, 15, 145, 679, 1000, 2330. Какую бы часть этого массива мы не взяли, она будет отсортированным массивом, следовательно, и массив вообще также отсортирован.
Отсюда следует идея рекурсивного определения. Сортировку кучи камней, можно свести к перераспределению камней двух примерно одинаковых меньших куч. И далее рекурсивно это же можно утверждать о каждой меньшей куче, разбивая ее на две,  пока не дойдем до куч из двух камней. Согласно, определения любой камень второй кучи должен быть тяжелее любого камня первой кучи.

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

В итоге получаем примерно отсортированный ряд камней. Точность сортировки определяется способностью выполнять оценку веса на «глазок». Понятно, что метод пригоден в случае сортировки предметов, которым можно каким-то образом присвоить численные значения. Идеально метод подходит для сортировки массивов, поэтому в программировании метод «Быстрой сортировки» имеет большое значение, если речь идет о больших объемах данных.  Пример. Дана куча камней 3, 67, 9, 1, 25, 9. Разделим эту кучу на две (3, 67, 9) и (1, 25, 9) Возьмем в качестве опорного камня камень 9. Тогда в левой куче должны оказаться меньшие, либо равные 9, в правой остальные. Например так: (3, 9, 1, 1) (67, 25). Сортировка второй кучи тривиальна (25, 67). К первой куче применим этот же прием, взяв в качестве опорного камень 3. Получаем: (3, 1, 1) (9) (25, 67). Последний шаг, очевиден.
 
Попробуем уйти от численных задач

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

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

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

(((1 + (1 + 1)) + (1 + 1 + 1)) + (1 + (1 + 1) + (1 + 1)))

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

                +
                ( + ) + ( + )        ( + )
                ( + )          ( + )

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

Пример шестой. Ханойская башня

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

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

Когда монахи завершат свою работу, мир завершит свое существование. Здесь, неплохо бы смотрелась графическая иллюстрация, но сайт Прозы, на которой я публикую свои книги, не имеет такой возможности в удобном формате. Поэтому будем представлять три алмазные подставки как три ряда чисел: A, B, C. Золотые диски представим числами. Большее число будет обозначать диск большего радиуса. Например, исходная Ханойская башня с четырьмя дисками будет выглядеть так:

A 4 3 2 1
B _____
C _____

Итак, где здесь рекурсия. Допустим, решена задача с перестановкой пирамиды 3 2 1 с подставки A на подставку B  с использованием подставки C. То есть, получена следующая конфигурация:

A 4
B 3 2 1
C _____

Тогда очевидно диск радиуса 4 можно переложить на подставку C  и получить следующее положение:

A _____
B 3 2 1
C 4

И мы получили новую, более простую задачу – переставить пирамиду 3 2 1 с подставки B на подставку С, с использованием подставки A.

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

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

Общее методологическое рассуждение

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

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

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

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

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

Для программиста реализацией рекурсии (исполнителем) является фрагмент программного кода выполняющего простые операции. Эта часть кода оформляется в виде специальной структуры называемой: подпрограммой, функцией, процедурой. Вычислительная система имеет возможность создавать копии таких процедур, каждая из которых получает набор данных, от предыдущей процедуры, выполняет его преобразование, передает следующей процедуре, останавливая собственную работу до получения ответа, после чего завершает свою деятельность и передает результат предшествующей процедуре. Нечто похожее может выполнить и индивидуальный разум. Сформулировав задачу Решатель – человек может фиксировать этапы рекурсивного спуска в памяти или на бумаге.
Различие между машинным вычислителем и человеком, в объеме рекурсивного спуска и соответственно в типе задач. Машина имеет возможность пройти очень длинную цепочку спуска, но ее класс задач пока ограничен вычислительными проблемами. Возможно, для систем ИИ допустима и человеческая версия рекурсии. Отметим, что задачи решаемые человеком могут иметь практически любой степень сложности, но ограниченной трудоемкости.

В заключение

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