На этом шаге мы рассмотрим построение нисходящей рекурсии.
Существует два разных стиля написания рекурсивных определений функций с использованием простой рекурсии ([1, с.72-73]): нисходящая рекурсия и восходящая рекурсия.
Нисходящая рекурсия
- Определение (описательное).
- Нисходящая рекурсия последовательно разбивает данную задачу на все более простые, пока не доходит до терминального случая (ситуации, когда продолжения рекурсии не требуется), в котором значение определяемой функции получается без использования её вызова (с другими значениями аргумента), характерного для рекурсивных определений. После этого ответ начинает "конструироваться" с помощью промежуточных результатов, передаваемых обратно вызывающим функциям.
Процесс написания рекурсивного определения функции распадается на отдельные шаги. Эти определения кажутся очевидными впоследствие, но их не всегда легко придумать. Трудность, по-видимому, в том, что мы должны повторно вызывать определяемую функцию в тот момент, когда еще не знаем, будет ли работать создаваемое определение функции.
Здесь нужно допустить, что мы уже имеем функцию, которая правильно работает для аргумента, равного n-1 и построить определение, которое будет работать для следующего случая, т.е. для n.
Приведём рецепт написания индуктивного определения функции в случае нисходящей рекурсии ([1, с.78-80]):
- (1) напишите определение для терминального случая (например, для числа 0);
- (2) предположите, что у вас есть определение функции, работающее для случая, наиболее близкого к терминальному (например, для n-1). Попытайтесь использовать его для построения выражения, которое годится для следующего случая при подъёме вверх;
- (3) соедините результаты пунктов (1) и (2), используя охраняющие или условные выражения;
- (4) проведите тестирование.
Построение функций с накапливающим параметром - приём не универсальный, и он не гарантирует получения хвостовой рекурсии.
Замечание (важное). В силу рецептурного характера сказанного выше, мы приводим большое количество примеров. Желательно, чтобы вы выполнили написанные функции на компьютере и попытались их улучшить. Это один из классических способов изучения рекурсивного программирования.
(1)Грей П. Логика, алгебра и базы данных.- М., Машиностроение,1989,- 368 с.
На следующем шаге мы рассмотрим восходящую рекурсию.
