FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Email: Нажмите что бы посмотреть
Теория
Рекурсивным называется любой объект, который частично определяется через себя.
Теория
Теория
Теория
Рекурсия вокруг нас…
Классическим примером бесконечной рекурсии являются два поставленные друг напротив друга зеркала: в них образуются два коридора из затухающих отражений зеркал.
Классическим примером конечной рекурсии является русская матрешка.
Рекурсия вокруг нас…
Н.В. Гоголь в повести «Портрет» описывает сон художника Черткова (сон третьего уровня рекурсии). Проснувшись от этого сна Чертков попадает на второй уровень рекурсии – во второй сон. Проснувшись от второго сна, он попадает в первый сон, от которого тоже придется проснуться.
"Мастер и Маргарита" - один из наиболее ярких рекурсивных романов.
Тема Иешуа и Пилата рекурсивно вызывается из темы Мастера и Маргариты. Кроме того, здесь так же используется прием "книга в книге". Мастер пишет роман об Иешуа и Пилате, текст которого сливается с текстом книги "Мастер и Маргарита".
Рекурсия вокруг нас…
Элементы использования рекурсии находим еще раньше у Шекспира. Гамлет ставит спектакль, где в упрощенном варианте описываются события трагедии.
В романее Л. Толстого «Война и мир» рекурсия отражает прошлое в настоящем и будущем.
Р. Бернс «Дом, который построил Джек» в переводе
С. Маршака
Вот дом,
Который построил Джек.
А это пшеница,
Которая в темном чулане хранится
В доме,
Который построил Джек
А это веселая птица-синица,
Которая часто ворует пшеницу,
Которая в темном чулане хранится.
Рекурсия вокруг нас…
В программировании рекурсия — вызов функции из неё же самой, непосредственно или через другие функции, например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Программирование
Важно!
Выполнение рекурсивного алгоритма можно представить следующим образом:
каждый рекурсивный вызов процедуры F порождает в памяти компьютера новую копию этой процедуры и запускает ее на выполнение со своими значениями входных параметров.
После того как процедура F завершила работу, выполнение программы продолжается со следующего оператора после вызова F.
Программирование
Выводится 1,2,3,4,5
Пока i >1 вызывается следующая процедура
Выводится i
5
4
3
2
1
5>1 Да
4>1 Да
3>1 Да
2>1 Да
1>1 Нет
Rec(4)
Rec(3)
Rec(2)
Rec(1)
Вывод(1)
Решение. Последовательно находим:
F(2) = F(1) + 2 = 3,
F(3) = F(2) + 3 = 6,
F(4) = F(3) + 4 = 10,
F(5) = F(4) +5 = 15.
Ответ: 15
Программирование
Складывая все эти числа, получаем 49
Программирование
Складывая все эти числа, получаем 79
Программирование
Решение:
Найдем значение процедуры:
F(6)=F(5)+2*F(4)
F(5)=F(4)+2*F(3)
F(4)=F(3)+2*F(2)
F(3)=F(2)+2*F(0)=F(2)+2*1=F(2)+2
F(2)=1
Следовательно:
F(3)=1+2=3
F(4)=3+2*1=5
F(5)=5+2*3=11
F(6)=11+2*5=21
Программирование
F(2)
F(4)
F(3)
F(8)
F(5)
F(4)
F(6)
F(8)
F(5)
8+4+5+2+3+4+6+8+5=45
!
Построенное дерево позволяет ответить на более сложный вопрос: «Что напечатает программа?»
Выписав значения узлов в порядке построения, получим:
2 4 8 5 3 6 4 8 5
Результат работы программы при ином расположении оператора печати n, в общем случае, отличается от данного.
Программирование
Решение (II способ):
При n<=4
F(n)=n+F(2n)+F(n+1)
При n>4
F(8)=8; F(7)=7; F(6)=6; F(5)=5
Найдем значение процедуры:
F(4)=4 +F(2*4)+F(4+1)=4+F(8)+F(5)=
=4+8+5=17
F(3)=3 +F(2*3)+F(3+1)=3+F(6)+F(4)=
=3+6+17=26
F(2)=2 +F(2*2)+F(2+1)=2+F(4)+F(3)=
=2+17+26=45
Программирование
Решение:
при n<=4 F(n)=F(2n)+F(n+1)+n
при n>4 F(n)=n
Найдем значение процедуры:
F(2)=F(2*2)+F(2+1)+2=F(4)+F(3)+2
F(3)=F(2*3)+F(3+1)+3=F(6)+F(4)+3
F(4)=F(2*4)+F(4+1)+4=F(8)+F(5)+4
F(2)=F(8)+F(5)+4+F(6)+F(8)+F(5)+4+3+2
Ответ:
8,5,4,6,8,5,4,3,2
Программирование
Решение:
при n<=4 F(n)=F(2n)+n +F(n+1)
при n>4 F(n)= «не печатает!»
Найдем значение процедуры:
F(2)=F(2*2)+2+F(2+1)=F(4)+2+F(3)
F(3)=F(2*3)+3+F(3+1)=F(6)+3+F(4)
F(4)=F(2*4)+4+F(4+1)=F(8)+4+F(5)
F(2)=4+2+F(3)=4+2+3+F(4)=4+2+3+4
Ответ:
4,2,3,4
Программирование
Решение:
при n>1 F(n)=F(n-2)+n +F(n div 2)
при n<=1 F(n)= «не печатает!»
Найдем значение процедуры:
F(6)=F(6-2)+6+F(6 div 2)=F(4)+6+F(3)
F(4)=F(4-2)+4+F(4 div 2)=F(2)+4+F(2)
F(3)=F(3-2)+3+ F(3 div 2)=F(1)+3+F(1)
F(2)=F(2-2)+2+ F(2 div 2)=F(0)+2+F(1)
F(6)=F(2)+4+F(2)+6+F(3)= =F(2)+4+F(2)+6+3=2+4+2+6+3
Ответ:
2,4,2,6,3
Программирование
Решение:
при n>1 F(n)=n+F(n-2) +F(n div 2)
при n<=1 F(n)=n
Найдем значение процедуры:
F(5)=5+F(5-2)+F(5 div 2)=5+F(3)+F(2)
F(3)=3+F(3-2)+F(3 div 2)=3+F(1)+F(1)
F(2)=2+F(2-2)+F(2 div 2)=2+F(0)+F(1)
Получим:
F(2)=2+0+1
F(3)=3+1+1
F(5)=5+3+1+1+2+0+1
Ответ: 5,3,1,1,2,0,1
Программирование
Решение:
при n>10 F(n)=‘*’+F(n-2)
при n<=10 F(n)=‘**’ +F(n-3)
при n<=1 G(n)=‘**’
Найдем значение процедуры:
F(20)=* +F(18)
F(18)=* +F(16)
F(16)=* +F(14)
F(14)=* +F(12)
F(12)=* +F(10)
F(10)=* + ** +F(7)
F(7)=* + ** +F(4)
F(4)=* + ** +F(1)
F(1)=* + **
Ответ: 17
F(1)=3
F(4)=3+3=6
F(7)=3+6=9
F(10)=3+9=12
F(12)=1+12=13
F(14)=1+13=14
F(16)=1+14=15
F(18)=1+15=16
F(20)=1+16=17
Программирование
Ответ: 64
Задачи на закрепление
Справка
при n<5
F(n)=n+F(n+1) +F(n+2)
при n>=5
F(n)=n
Справка
Программирование
Ответ: 15
Задачи на закрепление
Справка
при n>3
F(n)=n+F(n-1) +F(n-3)
при n<=3
F(n)=n
Справка
Ответ: 19
Ответ: 18
Ответ: 40
Ответ: 16
Ответ: 5
Ответ: 4
Интернет-ресурсы