Основы программирования: ТЕМА 10. РЕКУРСИЯ.

Если поставить два зеркала напротив друг друга и между ними поместить предмет, то получится бесконечное множество изображений, причем каждое из них содержит свое собственное. Любое из этих изображений можно рассматривать как рекурсивный объект, который частично состоит или определяется с помощью самого себя. Рекурсивные объекты обладают несколькими свойствами:

· простотой построения;

· несхожестью конечного результата с начальными данными;

· внутренним самоподобием.

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

1. единица есть натуральное число;

2. число, следующее за натуральным (т.е. больше его на единицу), есть натуральное число.

Определение, которое задает некоторый объект в терминах более простого случая этого же объекта, называется рекурсивным определением.

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

Рекурсия — это способ описания функций или процессов через самих себя.

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

1. «погружение» алгоритма в себя, т. е. применение определения «в обратную сторону», пока не будет найдено начальное определение, не являющееся рекурсивным;

2. последовательное построение от начального определения до определения с введенным в алгоритм значением.

СОДЕРЖАНИЕ:

• Рекурсивные объекты

• Рекурсивное определение

• Рекурсия

• Рекурсивный алгоритм

• Пример 1. Определение факториала (слайды 8-11)

• Пример 2. Вычисление степени с натуральным показателем (слайд 12)

• Пример 3. Вычисление чисел Фибоначчи (слайды 13-15)

• Пример 4. Решение задачи о Ханойских башнях (слайды 16-20)

• Вопросы и задания

• Источники