На этом шаге мы разберем, что скрывается за этим понятием.
Для решения меньших подзадач рекурсивные функции обычно вызывают сами себя. И тут у начинающего программиста возникают вполне резонные сомнения и вопросы: действительно ли написанная таким образом рекурсивная функция будет работать и допустимо ли в теле функции вызывать её саму, если она ещё не завершилась? И даже несмотря на то, что в языках программирования с поддержкой рекурсии функции могут вызывать сами себя, крайне важно поверить, что они работают правильно для подзадач меньшего размера. Эту уверенность, играющую ту же роль, что и гипотеза в доказательствах методом индукции, называют рекурсивной "убеждённостью". Она - один из краеугольных камней рекурсивного мышления и в то же время "крепкий орешек", о который программисты-новички рискуют сломать себе зубы. И конечно же, это не догма, принимаемая безраздумно. Следующий мысленный эксперимент поясняет её роль в рекурсивном мышлении.
Представьте, что вы находитесь в огромной классной комнате, и учитель просит вас найти сумму целых чисел от 1 до 100. Если вы не знаете формулы (1.12), вам пришлось бы выполнить 99 сложений. Но предположим, что вам разрешено переговариваться с одноклассниками, и среди них есть один "умный", который убеждён, что может сложить первые n положительных целых чисел, когда n < 99. В этом случае ваша задача стала бы гораздо проще: вы могли бы просто попросить его вычислить сумму первых 99 положительных целых чисел (она равна 4950), а вам бы осталось только добавить к ней 100, чтобы получить 5050. Несмотря на то что вы якобы пытаетесь схитрить или воспользоваться некой уловкой, такая стратегия, приведённая на рис. 1(a), - правильный способ (рекурсивного) мышления и решения задачи. При этом вы должны быть уверены лишь в том, что умный одноклассник действительно даст вам правильный ответ на ваш вопрос. Эта уверенность как раз и соответствует рекурсивной убеждённости.
Рис.1. Задача на устный счёт в классе. Учитель просит учеников сложить первые 100 положительных целых чисел. S(n) - сумма первых n положительных целых чисел
Для ответа на ваш вопрос у вашего одноклассника есть два пути. Если он действительно очень умён, то способен ответить на ваш вопрос без посторонней помощи, например применив формулу (1.12). Но это маловероятно ввиду сложности задачи. Поэтому, осознавая, что он не столь умён, как ему кажется, для получения ответа на заданный ему вопрос он, скорее всего, выберет другой путь и задаст аналогичный вопрос ещё одному "умному" однокласснику, то есть воспользуется вашей же стратегией. Иными словами, вы можете считать, что ваш друг - это просто ваш клон. Фактически при таком сценарии, представленном на рис. 1(b), все ученики в классе применили бы ваш подход. Отметим, что этот процесс явно рекурсивен: каждый ученик просит другого, чтобы тот решил более простую задачу (размер которой на каждом шаге уменьшается на 1), пока самый последний в этой цепочке ученик не даст ответ "1" для тривиального начального условия. Таким образом, каждый ученик может дать ответ всякому, кто попросит его вычислить полную сумму целых чисел, выполнив только одно-единственное сложение. Этот процесс продолжается до тех пор, пока вы не получите сумму первых 99 положительных целых чисел. После чего вы сможете правильно ответить на вопрос учителя, добавив к этой сумме 100. Стоит отметить, что процесс не заканчивается по достижении начального условия (это одна из главных ошибок в понимании студентами начального условия). Кроме первого этапа, когда ученики последовательно задают вопросы другим одноклассникам, пока один из них не даст тривиальный ответ "1", есть и второй - когда они вычисляют сумму и передают результат однокласснику.
Этот подход можно формализовать, как в (1.5), и закодировать, как в примере 1.1, где S(n - 1) или sum_first_naturals(n - 1) равносильны вашему обращению к однокласснику с просьбой решить подзадачу. Рекурсивная убеждённость заключается в вашей уверенности в том, что S(n - 1) в определении или sum_first_naturals(n - 1) в коде действительно дают правильный ответ.
Аналогично, при доказательстве методом индукции мы можем предположить, что процедура в целом должна быть правильной. Во-первых, ваш ответ будет верным, пока ваш одноклассник даёт вам правильный ответ. Но то же самое относится и к ученику, которого ваш одноклассник просит решить подзадачу. Это рассуждение может многократно применяться к каждому ученику до тех пор, пока, наконец, некий ученик не попросит другого сложить целые числа от 1 до 1. Так как последний ученик возвращает 1, что, конечно же, верно, все предыдущие ответы студентов должны быть по той же причине верными.
Всё это подразумевает, что программисты могут - и должны - выстраивать правильные рекурсивные условия, предполагая, что рекурсивные вызовы функции, включающие подобные им подзадачи меньшего размера, работают правильно. Неформально мы должны считать, что можем получить решения подзадач "бесплатно". Таким образом, если нам нужно решать различные задачи, то согласно декомпозиции на рисунке 1 4 шага нам нет нужды решать подобные исходной подзадачи, так как можно считать, что эти решения уже найдены. Конечно, нам нужно будет так или иначе переработать их (изменить, расширить, объединить и т. д.), чтобы создать рекурсивные условия. Наконец, рекурсивные алгоритмы завершаются благодаря начальным условиям, которые не только истинны, но и позволяют алгоритмам завершаться.
На следующем шаге мы рассмотрим императивное и декларативное программирование.
