Фрактали

Дерева

3, 2, 1.

0, 1, 2, 3.

В даній процедурі водно, що параметри процедури це межі зміни значень лічильника.

Нижче представлена ​​блок-схема, що показує послідовність виконання операторів для Rec(0,3)

Rec(3)

Виклик Rec(2)

Друк 3

Rec(2)

Виклик Rec(1)

Друк 2

Rec(1)

Виклик Rec(0)

Друк 1

Rec(0)

I=0

Друк 0

Початок

Кінець

Виклик Rec(3)

Процедура Rec викликається з параметром a = 3. У ній міститься виклик процедури Rec з параметром a = 2. Попередній виклик ще не завершився, тому створюється ще одна процедура і до закінчення її роботи перша процедура свою роботу не закінчує. Процес виклику закінчується, коли параметр a = 0. У цей момент одночасно виконуються 4 примірники процедури. Кількість одночасно виконуваних процедур називають глибиною рекурсії.

Четверта процедура (Rec (0)) надрукує число 0 і закінчить свою роботу. Після цього керування повертається до процедури, яка її викликала (Rec (1)) і друкується число 1. І так далі поки не завершаться всі процедури.

Ще одна графічна інтерпретація цієї процедури може виглядати наступним чином:

Виконання процедури Rec з параметром 3 складається з виконання процедури Rec з параметром 2 і друку числа 3. У свою чергу виконання процедури Rec з параметром 2 складається з виконання процедури Rec з параметром 1 і друку числа 2. І т. д.

Можна поміняти місцями рекурсивний виклик і оператор друку, як у наступному прикладі.

procedure Rec2(i: integer);

begin

writeln (i);

if i>0 then Rec2(i-1);

end;

Тоді результатом вихідного виклику буде друк чисел:

Зверніть увагу, що у наведених прикладах рекурсивний виклик стоїть всередині умовного оператора. Це необхідна умова для того, щоб рекурсія закінчилася. Також зверніть увагу, що сама себе процедура викликає з іншим параметром, не таким, з яким була викликана вона сама, це необхідно, для того щоб рекурсія не продовжувалася до нескінченності.

4. Імітація циклу за допомогою рекурсії

Деякі мови програмування не містять циклічних конструкцій зовсім, надаючи програмістам засоби організовувати повторення за допомогою рекурсії (наприклад, Пролог, де рекурсія - основний прийом програмування).

Якщо процедура викликає сама себе, то, по суті, це призводить до повторного виконання описаних в ній команд, що аналогічно роботі циклу.

Для прикладу зімітуємо роботу циклу for.

procedure Rec(n: integer); begin ifn >0 thenRec(n -1); writeln(n); end;	For i:=n downto 0 do writeln(i); або For i:=1 to n do writeln(n-i+1);
procedure Rec2(n: integer); begin writeln(n); if n>0 then Rec2(n-1); end;	For i:=1 to n do writeln(i);
procedure Rec3(n: integer); begin writeln(n); if n>0 then Rec3(n-1); writeln(n); end;	For i:=n downto 0 do writeln(i); For i:=1 to n do writeln(i);

5.Приклади використання рекурсивних алгоритмів

5.1 Переведення числа в двійкову систему.

Одержання цифр двійкового числа, як відомо, відбувається за допомогою ділення із залишком на підставу системи числення 2. Якщо є число, то його остання цифра в його двійковому поданні дорівнює

.

Взявши цілу части від ділення на 2:

,

отримаємо число, що має те ж двійкове представлення, але без останньої цифри. Таким чином, досить повторювати наведені дві операції поки поле чергового ділення не отримаємо цілу частину рівну 0. Без рекурсії це буде виглядати так:

while x>0 do

begin

c:=x mod 2;

x:=x div 2;

write(c);

end;

Проблема тут у тому, що цифри двійкового представлення обчислюються в зворотному порядку (спочатку останні). Щоб надрукувати число в нормальному вигляді доведеться запам'ятати всі цифри в елементах масиву і виводити в окремому циклі.

За допомогою рекурсії неважко домогтися виведення в правильному порядку без масиву і другого циклу. А саме:

procedure BinaryRepresentation(x: integer);

var

c, x: integer;

begin

{Первый блок. Выполняется в порядке вызова процедур}

c:= x mod 2;

x:= x div 2;

{Рекурсивный вызов}

if x>0 then

BinaryRepresentation(x);

{Второй блок. Выполняется в обратном порядке}

write(c);

end;

Взагалі ніякого виграшу ми не отримали. Цифри двійкового представлення зберігаються в локальних змінних, які є незалежними для кожного примірника рекурсивної процедури. Тобто, пам'ять заощадити не вдалося. Навіть навпаки, витрачаємо зайву пам'ять на зберігання багатьох локальних змінних x. Тим не менш, таке рішення є цікавим.

5.2. Рекурентні співвідношення: основні поняття

В основі розглянутих раніше алгоритмічних прийомів накопичення суми і твори лежить фундаментальна ідея про те, що результат обчислень на кожному кроці циклу повинен залежати від результату обчислень на попередньому кроці. Узагальненим математичним виразом цієї ідеї є рекурентні співвідношення.

Кажуть, що послідовність векторів задана рекурентним співвідношенням, якщо задано початковий вектор і функціональна залежність подальшого вектора від попереднього

Вектори можна інтерпретувати як набори значень змінних. Таким чином, вони характеризують стан обчислювального процесу. Функцію будемо розуміти як перетворення значень змінних на кожному кроці циклу.

Простим прикладом величини, що обчислюється за допомогою рекурентних співвідношень, є факторіал

Черговий факторіал можна обчислити за попереднім як:

Ввівши позначення, отримаємо співвідношення:

Кожне таке оновлення (x: = x * i) називається ітерацією, а процес повторення ітерацій - ітеріраційним.

Звернемо, однак, увагу, що співвідношення (1) є чисто рекурсивним визначенням послідовності та обчислення n-го елемента є насправді багаторазове взяття функції f від самої себе:

Так для факторіала:

x:= 1; for i:= 2 to n do x:= x * i; writeln(x); end;

function Factorial(n: integer): integer; begin if n > 1 then Factorial:= n * Factorial(n-1) else Factorial:= 1;

Слід розуміти, що виклик функцій тягне за собою деякі додаткові витрати, тому перший варіант обчислення факторіала буде кілька більш швидким. Взагалі ітераційні рішення працюють швидше рекурсивних.

Перш ніж переходити до ситуацій, коли рекурсія корисна, звернемо увагу ще на один приклад, де її використовувати не слід.

Розглянемо окремий випадок рекурентних співвідношень, коли наступне значення в послідовності залежить не від одного, а відразу від кількох попередніх значень. Прикладом може служити відома послідовність Фібоначчі, в якій кожен наступний елемент є сума двох попередніх:

function Fib(n: integer): integer; begin if n > 1 then Fib:= Fib(n-1) + Fib(n-2) else Fib:= 1; End

// x1, x2 – початкові умови (1, 1) // n – номер числа Фибоначчі function Fib(x1, x2, n: integer): integer; var x3: integer; begin if n > 1 then begin x3:= x2 + x1; x1:= x2; x2:= x3; Fib:= Fib(x1, x2, n-1); end else Fib:= x2; end;

Кожен виклик Fib створює одразу дві копії себе, кожна з копій - ще дві і т.д. Кількість операцій зростає з номером n експоненціально, хоча при ітераційному розв'язанні досить лінійного по n кількості операцій.

Насправді, наведений приклад вчить нас не КОЛИ рекурсію не слід використовувати, а тому ЯК її не слід використовувати. Зрештою, якщо існує швидке ітераційне (на базі циклів) рішення, то той же цикл можна реалізувати за допомогою рекурсивної процедури або функції.

Теоретичною базою для рекурсивних функцій, що викликають себе більше одного разу, служить розділ дискретної математики, що вивчає дерева.

Основні визначення. Способи зображення дерев

Визначення: Деревом будемо називати кінцеве безліч T, що складається з одного або більше вузлів, таких що:

а) є один спеціальний вузол, званий коренем даного дерева.

б) інші вузли (виключаючи корінь) містяться в попарно підмножинах, що не перетинаються, кожна з яких у свою чергу є деревом. Дерева називаються піддеревами даного дерева.

Це визначення є рекурсивним. Якщо коротко, то дерево це множина, що складається з кореня і приєднаних до нього піддерев, які теж є деревами. Дерево визначається через саме себе.

Але дане визначення осмислено, так як рекурсія скінченна. Кожне піддерево містить менше вузлів, ніж дерево, яке його утримує. Зрештою, ми приходимо до піддерев, що містить всього один вузол, а це вже зрозуміло, що таке.

Рис.. Дерево.

Графічно дерево можна зобразити і деякими іншими способами

Згідно з визначенням дерево являє собою систему вкладених множин, які або не перетинаються або повністю містяться одна в іншій. Такі множиниі можна зобразити як області на площині (рис. а). На рис. б вкладені множинр розміщені не на площині, а витягнуті в одну лінію. Рис. б також можна розглядати як схему деякої алгебраїчної формули, яка містить вкладені дужки. Рис. в дає ще один популярний спосіб зображення деревовидної структури у вигляді ступінчатого списку.

5.4. Швидкі сортування

Прості методи сортування на зразок методу вибору або методу бульбашки сортують масив з n елементів за O(n2) операцій. Однак за допомогою принципу «розділяй і володарюй» вдається побудувати більш швидкі, що працюють за O (n log2 n) алгоритми. Суть цього принципу в тому, що рішення виходить шляхом рекурсивного поділу завдання на кілька простих підзадач того ж типу до тих пір, поки вони не стануть елементарними.

Алгоритм 1: (quicksort).

1. Вибирається опорний елемент (наприклад, перший або випадковий).

2. Реорганізуємо масив так, щоб спочатку йшли елементи менші опорного, потім рівні йому, потім великі. Для цього достатньо пам'ятати, скільки було знайдено менших (m1) і великих (m2), ніж опорний і ставити черговий елемент на місце з індексом m1, а черговий більший на місце з індексом n-1-m2.

Після виконання такої операції опорний елемент і рівні йому стоять на своєму місці, їх переставляти більше не доведеться. Між «меншою» і «більшою» частинаи масиву перестановок також бути не може. Тобто ці частини можна сортувати незалежно один від одного.

3. Якщо «менша» або «більша» частина складається з одного елемента, то вона вже відсортована і робити нічого не треба. Інакше сортуємо ці частини за допомогою алгоритму швидкого сортування (тобто, виконуємо для неї кроки 1-3).

Як бачите, швидке сортування складається з виконання кроків 1 і 2 та рекурсивного виклику алгоритму для одержані частин масиву.

Багато об'єктів навколишнього світу мають властивість "самоподібності".

Фракталами називають геометричні фігури, що володіють властивістю самоподібності, тобто складаються з частин, подібних всій фігурі.

Математичний опис нескінченно дробимістю об'єктів рівняннями ліній або поверхонь надзвичайно громіздко через неосяжної кількості найдрібніших об'єктів. Для подолання цієї труднощі математиком Дослідницького центру корпорації IBM Бенуа Мандельброт в 1975 році було введено термін "фрактал" (від латинського fractus - роздроблений, розбитий, що складається з фрагментів), а в 1982 році опублікована основоположна книга "Фрактальна геометрія природи", де описані фрактальні множини, їх властивості, методи одержання та зображення.

Класичним прикладом є крива Коха, побудова якої показано на рис. 12. Спочатку береться відрізок прямої (рис. 12а). Він ділиться на три частини, середня частина вилучається і замість неї будується кут (рис. 12б), сторони якого дорівнюють довжині вилученого відрізка (тобто 1/3 від довжини вихідного відрізка). Така операція повторюється з кожним з вийшов 4-х відрізків (рис. 12в). І так далі (мал. 12г). Крива Коха виходить після нескінченного числа таких ітерацій. На практиці побудова можна припинити, коли розмір деталей виявиться менше дозволу екрану (рис. 12д).

Фрактали, по суті, рекурсивні структури та їх побудову природно проводити за допомогою рекурсивних процедур.

Ще одним прикладом може служити деревце на рис. Воно також містить частини, подібні всьому дереву в цілому, що робить його фракталом.

Розглянемо алгоритм малювання деревця, зображеного на рис.. Якщо кожну лінію вважати вузлом, то дане зображення цілком задовольняє визначенню дерева, даному в попередньому розділі.

Рекурсивна процедура, очевидно повинна малювати одну лінію (стовбур до першого розгалуження), а потім викликати сама себе для малювання двох піддерев. Піддерев відрізняються від базового дерева координатами початкової точки, кутом повороту, довжиною стовбура і кількістю розгалужень (на одне менше). Всі ці відмінності слід зробити параметрами рекурсивної процедури.

Рекурсивна програма побудови сніжинки

Зображення будується за наступним правилом: будується коло із заданим радіусом r. Потім на діаметрально протилежних точках кола (x-r і x + r) будується знову окружність меншого радіуса (r = 3 r / 5). Для кожної меншою окружності на діаметрально протилежних точках знову будується коло меншого радіусу, і т.д., поки радіус не зменшиться до 10.

Можна також будувати аналогічні сніжинки

"Множина Кантора".

Даний малюнок утворений квадратами. Кожний наступний квадрат в чотири рази менше попереднього. Центр кожного наступного квадрата лежить у вершині попереднього квадрата і т.д. Так як малюнок складається з однотипних елементів, і є явна залежність, як розмірів, так і положення, при створенні даного малюнка можна використовувати рекурсію.

Самим знаменитим прикладом майданного геометричного фрактала є трикутник Серпінського (див. рис.6), що будується шляхом розбиття трикутника, необов'язково рівностороннього - середніми лініями на чотири подібних трикутника,

.

Дата добавления: 2014-01-05