Основы программирования: ТЕМА 10. РЕКУРСИЯ.
презентация к уроку по информатике и икт (9 класс) по теме

Слайд 1

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

Слайд 2

рекурсия Тема 10. 03.11.2013 Цыбикова Т.Р. 2

Слайд 3

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

Слайд 4

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

Слайд 5

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

Слайд 6

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

Слайд 7

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

Слайд 8

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

Слайд 9

03.11.2013 Цыбикова Т.Р. 9 В содержание

Слайд 10

Выполним программу Е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 условного оператора. 03.11.2013 Цыбикова Т.Р. 10 В содержание

Слайд 11

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

Слайд 12

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

Слайд 13

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

Слайд 14

Для чисел Фибоначчи используется следующее рекурсивное определение Для чисел Фибоначчи используется следующее рекурсивное определение: (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 03.11.2013 Цыбикова Т.Р. 14 В содержание

Слайд 15

Количество действий в данных вычислениях с использованием рекурсивного определения чисел Фибоначчи резко возрастает, потому что это определение ссылается само на себя дважды. При вычислении факториала количество действий при выполнении программы с рекурсивной функцией и примера E 9 одинаково. 03.11.2013 Цыбикова Т.Р. 15 В содержание

Слайд 16

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

Слайд 17

03.11.2013 Цыбикова Т.Р. 17 В содержание

Слайд 18

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

Слайд 19

Программа имеет вид: 03.11.2013 Цыбикова Т.Р. 19 В содержание

Слайд 20

Результат работы программы для 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 03.11.2013 Цыбикова Т.Р. 20 В содержание

Слайд 21

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

Слайд 22

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