🗊Презентация Рекурсия. Определение факториала. (Тема 10)

Основы программирования Учитель информатики и ИКТ ГОУ г.Москвы СОШ №310 «У Чистых прудов» Цыбикова Т.Р.

рекурсия Тема 10.

СОДЕРЖАНИЕ Рекурсивные объекты Рекурсивное определение Рекурсия Рекурсивный алгоритм Пример 1. Определение факториала (слайды 8-11) Пример 2. Вычисление степени с натуральным показателем (слайд 12) Пример 3. Вычисление чисел Фибоначчи (слайды 13-15) Пример 4. Решение задачи о Ханойских башнях (слайды 16-20) Вопросы и задания Источники

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

Рекурсивное определение В математике встречаются рекурсивные определения, позволяющие описать объекты через самих себя. К таким определениям относится, например, определение натурального числа: единица есть натуральное число; число, следующее за натуральным (т.е. больше его на единицу), есть натуральное число. Определение, которое задает некоторый объект в терминах более простого случая этого же объекта, называется рекурсивным определением.

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

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

Пример 1. Определение факториала Наиболее распространенным рекурсивным определением является определение факториала (нерекурсивное вычисление факториала приведено в примере Е9):  (a) 1! = 1, (b) n > 1, n: = n*(n - 1)! На основе этого определения можно записать программу вычисления факториала, использующую рекурсивную функцию.

Выполним программу Е25 для n=4. Выполним программу Е25 для n=4. Рекурсивная функция будет работать следующим образом (при вызове функции значение n присваивается переменной x). Сначала осуществляется «погружение», работает оператор ветви else условного оператора: 1-й шаг: х = 4, х - 1 = 3, выполняется промежуточное вычисление 4! = 4 * 3! 2-й шаг: х = 3, х - 1 = 2, выполняется промежуточное вычисление 3! = 3 * 2! 3-й шаг: х = 2, х - 1 = 1, выполняется промежуточное вычисление 2! = 2 * 1! 4-й шаг (последний): 1! = 1 по начальному определению, работает оператор F: = 1 ветви then условного оператора.

Следующий этап выполнения рекурсивного алгоритма Следующий этап выполнения рекурсивного алгоритма — построение «прямого» определения, от начального до получения результата с исходными для алгоритма данными (числом 4). При этом осуществляется подстановка предыдущих вычислений (более поздних шагов) в более ранние: 5-й шаг: 2! = 2 * 1 = 2 6-й шаг: 3! = 3 * 2 = 6 7-й шаг: 4! = 4 * 6 = 24 — получен результат, он возвращается в плавную программу и присваивается переменной Y.

Пример 2. Вычисление степени с натуральным показателем Вычисление степени с натуральным показателем можно определить рекурсивно: (а) x0 = 1 (б) k>0: хk = x*xk-1 Этому определению соответствует рекурсивная функция power(k,x). Программа имеет вид:

Пример 3. Вычисление чисел Фибоначчи Вычисление чисел Фибоначчи. Итальянский математик Фибоначчи придумал последовательность натуральных чисел: 1, 1, 2, 3, 5, 8. 13, ... . Первые два члена последовательности равны единице, а каждый, начиная с третьего, равен сумме двух предыдущих. Для чисел Фибоначчи верно соотношение: Fk=Fk-1 + Fk-2 Рекурсивная функция получения значения n-го числа Фибоначчи имеет вид:

Для чисел Фибоначчи используется следующее рекурсивное определение Для чисел Фибоначчи используется следующее рекурсивное определение: (a) n = 1, n = 2: fib(n) = 1 (b) n > 2: fib(n) = fib(n - 2) + fib(n - 1) Для того чтобы определить fib(6), применяя данное рекурсивное определение, надо вычислить: fib(6) = fib(4) + fib(5) = fib(2) + fib(3) + fib(5)= =1 + fib(3) + fib(5)= =1 + fib(1) + fib(2) + fib(5) = = 1 + 1 + 1 + fib(5) = = 3 + fib(3) + fib(4) = = 3 + fib(1) + fib (2) + fib(4) = =3 + 1 + 1 + fib(4) = =5 + fib(2) + fib(3) = =5 + 1 + fib(1) + fib(2) = 6+1 + 1= 8

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

Пример 4. Решение задачи о Ханойских башнях Рекурсивные алгоритмы могут быть оформлены и в виде процедур. Примером такой процедуры является решение задачи о Ханойских башнях. Эта задача связана с легендой о том, что в одном из восточных храмов находится бронзовая плита с тремя алмазными стержнями. На один из них при сотворении мира нанизали 64 диска из чистого золота так, как показано на рисунке 36. Жрецы должны переносить диски с одного стержня на другой, следуя следующим законам: диски можно перемещать только по одному; нельзя класть больший диск на меньший. Согласно легенде, когда все диски будут перенесены с одного стержня на другой, наступит конец света.

Решение этой задачи реализовано в виде рекурсивного алгоритма Решение этой задачи реализовано в виде рекурсивного алгоритма, который представляет собой инструкцию по перемещению дисков. Сформулируем задачу, присвоив имена стержням (A, B, C) и номера дискам (от 1 до n). Надо перенести диски со стержня A на стержень C, используя B как вспомогательный и следуя приведенным выше правилам переноса дисков. Алгоритм на естественном языке имеет вид: если n = 0, остановиться; переместить верхние n - 1 дисков со стержня A на стержень B, используя стержень C как вспомогательный; переместить оставшийся диск со стержня A на стержень C; переместить n - 1 дисков со стержня B на стержень C, используя стержень A как вспомогательный. В процедуре появляется новый тип данных — char, значение этого типа — один символ, заключенный в апострофы.

Программа имеет вид:

Результат работы программы для n=3 Результат работы программы для n=3 — это инструкция из 7 пунктов (n= 4 — инструкция из 15 пунктов): переместить диск 1 со стержня A на стержень C переместить диск 2 со стержня A на стержень B переместить диск 1 со стержня C на стержень B переместить диск 3 со стержня A на стержень C переместить диск 1 со стержня B на стержень A переместить диск 2 со стержня B на стержень C переместить диск 1 со стержня A на стержень C

Вопросы и задания Что такое рекурсивный объект и каковы его свойства? Приведите примеры рекурсивного определения в математике. Что такое рекурсия? Как выполняется рекурсивный алгоритм? Поясните выполнения рекурсивной функции вычисления степени с натуральным показателем. Напишите главную программу для вычисления n-го числа Фибоначчи. Почему использовать рекурсивный алгоритм вычисления n-го числа Фибоначчи невыгодно? Определите рекурсивно умножение как сложение и деление как вычитание и оформите алгоритмы в виде рекурсивных функций с вызовом из главных программ.

Литература А.А.Кузнецов, Н.В.Ипатова «Основы информатики», 8-9 кл.: Раздел 3. ОСНОВЫ ПРОГРАММИРОВАНИЯ, С.130-135