Рекурсия: плохо или хорошо?

Полный текст статьи опубликован в интернет-журнале "Потенциал" по вот этому адресу

Пупышев Вячеслав Викторович - старший преподаватель кафедры математического обеспечения ЭВМ Удмуртского государственного университета.

Содержание

Понятие рекурсии
Числа Фибоначчи
Проблемы рекурсии и как их решать
Задача о золотой горе
Задача "Сделай палиндром"
Алгоритм Евклида
Задачи для самостоятельного решения
Задача коммивояжёра
Заключение
Литература
Снежинка Коха

Понятие рекурсии

Рекурсия — это жемчужина теории алгоритмов. Это первое, с чем знакомят школьников, после того, как они овладеют процедурами ввода и вывода данных, элементарными арифметическими операциями, оператором цикла и условного оператора. Простота рекурсии обманчива. Она таит в себе множество ловушек и сложных моментов, но и преподносит много подарков. Давно известен такой математический приём, как сведение задачи к нескольким более простым. Затем простые задачи можно снова свести к ещё более простым и так далее, пока не доберёмся до самых элементарных задач. Представьте, что нужно пройти 1000 шагов. Для решения этой задачи вы делаете один шаг, и остаётся 999 шагов. Таким образом, задача упростилась. Сделав такое упрощение 999 раз, дойдём до самой элементарной задачи - сделать один шаг. Конечно, этот пример слишком прост. Далее мы рассмотрим несколько более сложных примеров, поясняющих идею рекурсии и демонстрирующих её хорошие и плохие стороны. Прежде всего важно заметить аналогию рекурсии с понятием математической индукции. У рекурсии так же как и в методе математической индукции есть - аргументы, для которых значения функции определены (элементарные задачи), и шаг рекурсии - способ сведения данной задачи к более простым задачам (тем, которые мы уже умеем решать).

Продолжение смотрите здесь

Рис