Информатика и технология программирования


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


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

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



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



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



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




Начало  Назад  Вперед



Книжный магазин