Экономико-математическое моделирование : Рекурсия

Рекурсия

Нужно быть очень терпеливым,

чтобы научиться терпению.

Е. Лец

Нельзя говорить нельзя.

Д. Араго

Введение

Полезность, важность и необходимость рекурсии, как одного из концептуальных методов решения практических задач подчеркивалась многими мэтрами информатики. Сошлемся лишь на двух лауреатов премии Тьюринга: американского специалиста по системному программированию Д.Кнута и английского теоретика информатики Ч.Хоара.

Д.Кнут широко использовал рекурсию при изложении материала в ставшем уже классическим его трехтомном выпуске “Искусство программирования для ЭВМ” [1-3]. Кроме того, он предполагал продолжить издание книг этой серии и в четвертом томе одну из двух глав назвать “Рекурсия”, полностью посвятив её рекурсивным методам решения задач [1, стр.11]. К великому сожалению, тома с 4 по 7 до сих пор не вышли. Однако в настоящее время появилась надежда, что в ближайшие годы (1999г.-2004г.) они будут дописаны и опубликованы [9].

Ч.Хоару принадлежат следующие слова “Следует отдать должное гению разработчиков Алгола-60 за то, что они включили в свой язык рекурсию и дали мне тем самым возможность весьма элегантно описать мое изобретение (речь идет о так называемой быстрой сортировке - Quick Sort). Сделать возможным изящное выражение хороших мыслей - я считал это наивысшей целью проекта языка программирования” [4, стр. 176]. К этому лишь следует добавить, что, на сегодняшний день, практически все действующие языки программирования поддерживают рекурсию.

В данном пособии дается неформальное понятие рекурсии, рассказываетс