1 1 Макаренко Олег Новый день Издательство Харьков

2 2 УДК (73) ББК 84 (7Сое) П14 Подписано в печать Формат 70х90/32 Усл. Печ. Л. 11,6. Доп. Тираж экз. Заказ СБ 3052 Макренко О.А. П14 Украина в годы Второй Мировой войны: [историческая публицистика]/Олег Макаренко; Исторические правки А.П.Аниссимова. – Новый день 18 с. – (История ) Рекурсией называется такая конструкция, при которой функция вызывает саму себя. Различают прямую и косвенную рекурсии. Функция называется прямо рекурсивной, если содержит в своем теле вызов самой себя. Если же функция вызывает другую функцию, которая в свою очередь вызывает первую, то такая функция называется косвенно рекурсивной. Рассмотрим классические примеры использования рекурсии - реализацию операции возведения в степень и вычисление факториала числа. Заметим, что эти примеры являются классическими только из - за их удобства для объяснения понятия рекурсии, однако они не дают выигрыша в программной реализации по сравнению с итерационным способом решения этих задач.

3 3

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

5 5 Этот пример основан на том, что x y равно x*x (y-1). В этом коде задача вычисления 2 4 разбивается на вычисление 2*2³. Затем 2*2³ разбивается на 2*2² и так до тех пор, пока показатель не станет равным нулю. Обычное решение этого примера выглядит так: Кроме того, что этот код намного легче понять, он еще и более эффективен, поскольку проход цикла обходится "дешевле" вызова функции.

6 6 Для отрицательного аргумента функция возвращает нулевое значение, так как факториал отрицательного числа не существует по определению. Для нулевого параметра функция возвращает значение 1, поскольку 0! = 1. Т. е. происходит вычисление произведения: k * (k - 1) * (k - 2) *... * 3 * 2 * 1 * 1 Последовательность рекурсивных вызовов прерывается только при вызове fact(0), который и приводит к последнему значению 1 в произведении, так как последнее выражение, из которого вызывается функция, имеет вид 1 * fact(1 - 1). Обычно факториал можно вычислить так:

7 7 Подпрограммы в Паскале могут обращаться сами к себе. Такое обращение называется рекурсией. Для того чтобы такое обращение не было бесконечным, в тексте подпрограммы должно быть условие, по достижению которого дальнейшее обращение к подпрограмме не происходит. Т. е. подобие шага. Пример. Рассмотрим математическую головоломку из книги Ж. Арсака « Программирование игр и головоломок ». Построим последовательность чисел следующим образом : возьмем целое число i>1. Следующий член последовательности равен i/2, если i четное, и 3 i+1, если i нечетное. Если i=1, то последовательность останавливается. Применение рекурсии позволило решить задачу без использования циклов, как в основной программе, так и в процедуре. К содержанию К содержанию

8 8 Пример программы с использованием рекурсии Program Arsac; Var perv: word; Procedure recov (i: word); Begin Writeln (i); If i=1 then exit; If odd(i) then recov (3*i+1) else recov (i div 2); End; Begin Write ( введите первое значение ); readln (perv); recov(perv); Readln ; End.

9 9 Программист разрабатывает программу, сводя исходную задачу к более простым. Среди этих задач может оказаться и первоначальная, но в упрощенной форме. Например, для вычисления F( N) может понадобиться вычислить F( N-1). Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции. Алгоритм, который является своей собственной частью, называется рекурсивным. Часто в основе такого алгоритма лежит рекурсивное определение. Пример рекурсивного алгоритма N! = ( N-1)!* N, если N=0, то N!= 1 Любое рекурсивное определение состоит из двух частей. Одна часть определяет понятие через него же, другая часть – через иные понятия. Пример рекурсивного алгоритма 2n= 2 n-1*2, если n=0, то 2 n= 1 Процедура является рекурсивной, если она обращается сама к себе прямо или через другие процедуры.

Пример рекурсивной функции вычисления факториала : Function fcal (N: integer) : longint; Begin If N= 0 then fcal := 1 Else fcal := fcal (N-1) * N End; Пример рекурсивной процедуры, возводящей число в степень : Procedure dev (X: real; N: integer; var Y: real); Begin If N=0 then Y:= 1 Else Begin Dev (X, N-1,Y); Y:= Y*X; End ; 10

Рекурсивная программа построения снежинки Написать программу, строящую на экране изображение: Изображение строится по следующему правилу: строится окружность с заданным радиусом r. Затем на противоположных точках окружности ( x- r и x+ r)строится вновь окружность меньшего радиуса ( r=3 r/5). Для каждой меньшей окружности на противоположных точках вновь строится окружность меньшего радиуса, и т.д., пока радиус не уменьшится до К содержанию К содержанию

Пример рекурсивной программы построения окружностей program recurs; uses graph; var x,y,r,d,m:integer; procedure kolo(x,y,r:integer); var i:integer; begin if r

- Как герой Мольера не знал, что он разговаривает прозой, так и мы зачастую не знаем, что пользуемся рекурсией. Научно выражаясь : Рекурсия метод определения класса объектов или методов предварительным заданием одного или нескольких ( обычно простых ) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса. Другими словами, рекурсия частичное определение объекта через себя, определение объекта с использованием ранее определённых. Рекурсия используется, когда можно выделить самовоспроизведение задачи. 13 К содержанию К содержанию

- В математике Факториал целого неотрицательного числа n обозначается n! и определяется как n!=n×(n-1)! при n>0 и n!=1 при n=0 Практически все геометрические фракталы задаются в форме бесконечной рекурсии. Треугольник Серпинского. - Рекурсия в физике Классическим примером бесконечной рекурсии являются два поставленные друг напротив друга зеркала : в них образуются два коридора из затухающих отражений зеркал. Другим примером бесконечной рекурсии является эффект самовозбуждения ( положительной обратной связи ) у электронных схем усиления, когда сигнал с выхода попадает на вход, усиливается, снова попадает на вход схемы и снова усиливается. Усилители, для которых такой режим работы является штатным, называются автогенераторы. 14

- Рекурсия в языке и литературе Пример рекурсивной словарной статьи : рекурсия см. рекурсия « У попа была собака …» - типичная рекурсия У попа была собака, он её любил Она съела кусок мяса, он её убил В землю закопал, Надпись написал : « У попа была собака, он её любил Она съела кусок мяса, он её убил В землю закопал, Надпись написал : « У попа была собака …» - типичная рекурсия У попа была собака, он её любил Она съела кусок мяса, он её убил В землю закопал, Надпись написал : « У попа была собака, он её любил Она съела кусок мяса, он её убил В землю закопал, Надпись написал : Рассказ о сепульках (« Звёздные дневники Йона Тихого »), в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье « сепульки ». Рассказ о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную, и поручить решение ей ( итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей ). 15

- Чтобы понять рекурсию, нужно сначала понять рекурсию. Эффект Droste - термин для изображения специфического вида рекурсивного изображения. Изображение включает уменьшенный собственный вариант самого себя. Этот более малый вариант после этого показывает даже более малый вариант себя, и так далее. Практически это продолжается пока разрешение изображения позволяет уменьшает размер. Термин был введен в честь Droste, голландского какао. 16

Рекурсия в сюжете Первым романом, удивившим читателей приемом рекурсии, был "Дон Кихот". Сервантес все время пытался смешивать два мира: мир читателя и мир книги. У Сервантеса главный процесс не просто книга, но книга плюс читатель. В шестой главе цирюльник, осматривая библиотеку Дон Кихота, находит книгу Сервантеса и высказывает суждения о писателе. Вымысел Сервантеса рассуждает о нем. В начале девятой главы сообщается, что роман переведен с арабского и что Сервантес купил его на рынке. Наконец, во второй части романа персонажи уже прочли первую часть. Элементы использования рекурсии находим еще раньше у Шекспира. Гамлет ставит спектакль, где в упрощенном варианте описываются события трагедии. " Мастер и Маргарита " - один из наиболее ярких рекурсивных романов. Развивается одна алгоритмическая схема, используемая в разных процессах : Мастер и Маргарита, Иешуа и Пилат, Воланд и компания. Тема Иешуа и Пилата рекурсивно вызывается из темы Мастера и Маргариты. Кроме того, здесь также используется прием " книга в книге ". Мастер пишет роман об Иешуа и Пилате, текст которого сливается с текстом книги " Мастер и Маргарита ". 17

18 К содержанию К содержанию

Исключительные права на публикацию принадлежат издательству «Новый день» Литературно-научное произведение Макаренко Олег Рекурсия ООО «Новый день» , Украина, Харьковская обл., г. Щелково, ул. Заречная, д. 96 Наши электронные адреса Информационные источники: Ответственные редакторы: Е.А. Барзова, Г.Г. Мурадян Компьютерная вёрстка: В.А. Смехов Технический редактор В. Кортикова 19