На этом шаге мы рассмотрим правила написания рекурсивных определений.

    Имеется три разных стиля рекурсивных определений; мы назовем их

• восходящей,
• нисходящей рекурсиями и
• рекурсией по дереву [1,с.72-73].

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

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

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

    Приведем вариант вычисления функции факториал с помощью этой техники:

   (DEFUN FACT1 (LAMBDA (N)
      (COND ( (EQ N 1) 1 )
            (  T  (TIMES N (FACT1 (DIFFERENCE N 1))) ))))

   (DEFUN DCOPY (LAMBDA (LST)
      (COND ( (NULL LST) NIL )
            (  T  (CONS (CAR LST) (DCOPY (CDR LST))) ))))

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

    Мы можем записать восходящую версию функции FAC следующим образом:

   (DEFUN FAC (LAMBDA (N)
      (FACT N 1)
   ))
   ; --------------------- 
   (DEFUN FACT (LAMBDA (N W)
      (COND ( (EQ N 0) W )
            (  T  (FACT (- N 1) (* N W)) ))))

    Здесь W - параметр рабочей памяти, применяемый для формирования результатов. Так как первоначальная функция имеет только один параметр, приходится определить вспомогательную функцию FACT с дополнительным параметром и при первом вызове функции FACT этот параметр надо инициализировать (придать ему начальное значение).

    Вычисление можно производить путем подстановки:

   FAC (3) = FACT (3,1) = FACT (2,3*1) = FACT (1,2*3*1) =
           = FACT (0,1*2*3*1) =1*2*3*1 = 6

    Мы видим, что результат формируется здесь в параметре рабочей памяти и замечаем, что его значение известно на каждом шаге, хотя мы и записываем его в виде выражения вроде 2*3*1. В противоположность этому нисходящая версия FAC дает промежуточные результаты в виде 3*2*FACT1(1), и мы не можем вычислить это значение, пока не знаем FACT1(1).

    Приведем еще один пример восходящей рекурсии для "обращения" списка:

   (DEFUN UCOPY (LAMBDA (LST)
      (COP LST NIL)))
   ; ---------------------- 
   (DEFUN COP (LAMBDA (LST W)
      (COND ( (NULL LST) W )
            (  T  (COP (CDR LST) (CONS (CAR LST) W)) ))))

    Рекурсия по дереву (параллельная рекурсия) - это еще один тип рекурсии, который приходится использовать даже в "обычном" программировании с помощью присваиваний. Она используется для обхода древовидной структуры, т.е. списка, элементы которого могут сами быть списками. С параллельной рекурсией и примерами ее использования вы познакомитесь в соответствующем разделе.

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

    Здесь нужно допустить, что мы уже имеем функцию, которая правильно работает для аргумента, равного N-1 или (CDR LST) и построить определение, которое будет работать для следующего случая (т.е. для числа N или списка LST).

    Рецепты (!) для написания определений функций в этих трех случаях таковы [1, с.78-80].

1. Нисходящая рекурсия (хвостовая рекурсия).
   • Напишите определение для терминального случая, например, для числа 0 или пустого списка NIL.
   • Далее предположите, что у вас есть определение функции, работающее для случая, наиболее близкого к терминальному (т.е. для N-1 или хвоста списка). Попытайтесь (!) применить его, чтобы построить выражение, которое годится для следующего случая при подъеме вверх.
   • Соедините результаты пунктов 1 и 2 в условное выражение. Тщательно тестируйте его на примерах.
2. Восходящая рекурсия.
   • Придумайте (!) функцию, имеющую один или несколько параметров типа рабочей памяти, в одном из которых будет строиться результат.
   • Для терминального случая положите значение функции равным параметру типа рабочей памяти.
   • Для нетерминального случая повторно вызовите функцию с новыми значениями параметров, выраженными через старые.
   • Вызовите функцию с начальными значениями параметров типа рабочей памяти.
   • Тестируйте определение функции на примерах и "подгоняйте", если это нужно, начальные значения.
3. Рекурсия по дереву.
   • Примените предикат (ATOM LST) и, если потребуется (NULL LST), чтобы распознать терминальный случай.
   • В общем случае предположите, что ваша функция правильно работает для (CAR LST) и (CDR LST), и напишите выражение для комбинации этих значений.

    В силу рецептурного характера наших советов, в разделах, посвященных рекурсии мы приводим большое количество примеров. Желательно, чтобы читатель выполнил написанные программы на компьютере и попытался их улучшить. Это один из самых известных способов изучения рекурсивного программирования!

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

Предыдущий шаг Содержание Следующий шаг