Философские аспекты рекурсии

Рекурсивные функции дают богатый материал для размышлений о процессе программирования вообще и об его связи с другими областями деятельности. В частности, принцип программирования рекурсивных функций имеет много общего с методом математической индукции. Напомним, что этот метод используется для доказательства корректности утверждений для бесконечной последовательности состояний, а именно : если утверждение верно в начальном состоянии, а из его справедливости в n-м состоянии можно доказать его справедливость в n+1-м состоянии, то такое утверждение будет справедливым всегда. Этот принцип неявно и применялся нами при разработке рекурсивных функций. Действительно, сама рекурсивная функция представляет собой переход из n-го в n+1 состояние некоторого процесса. Если этот переход корректен, то есть соблюдение некоторых условий на входе функции приводит к их соблюдению на выходе (то есть в рекурсивном вызове), то эти условия будут соблюдаться во всей цепочке состояний (при безусловной корректности начального). Отсюда следует, что самое важное в определении рекурсии - выделить те условия, которые соблюдаются во всех точках процесса и обеспечить их справедливость от входа в рекурсивную функцию до ее рекурсивного вызова. При этом " категорически не приветствуется" заглядывать в следующий шаг рекурсии или интересоваться состоянием процесса на предыдущем шаге. Да и в этом нет необходимости с точки зрения приведенного здесь метода доказательства.

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

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

-обобщенные начальные условия шага - формальные параметры функции ;

-начальные условия следующего шага - фактические параметры рекурсивного вызова ;

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

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

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

Содержание раздела