Зміст
Рекурсія. . . . . . . . . . . . . . . . . . . .
. . . . . . 2
Приклад 1. . . . . . . . . . . . . . . . . . .
. . . . . . . 2
Приклад 2. . . . . . . . . . . . . . . . . . .
. . . . . . . 3
Приклад 3. . . . . . . . . . . . . . . . . . .
. . . . . . . 4
Приклад 4. . . . . . . . . . . . . . . . . . .
. . . . . . . 4
Приклад 5. . . . . . . . . . . . . . . . . . . .
. . . . . . 6
Рекурсія.
рекурсією називається ситуація, коли процедура або функція сама себевикликає. Ось типова конструкція такого роду:
procedure proc (i: integer); begin anweisungen1; if bedingung then proc (i +1); anweisungen2; end;
Виклик proc (1) означає, що proc викликає себе раз по раз з допомогоюproc (2), proc (3), .. до тих пір, поки умова bedingung не скасує новийвиклик. При кожному виклику виконується оператор anweisungen 1, після чогопорядок виконання операторів переривається новим викликом proc (i +1). Щобдля кожного виклику був відпрацьований і оператор anweisungen2, всі локальнізмінні процедури зберігаються в стек. Стеком є структурамагазинного типу LIFO (Last In First Out), тобто якщо, наприклад, приproc (10) умова більше не виконується, anweisungen2 виконується ззначеннями, оброблюваними у зворотному порядку для proc (9), ..., proc (1).
Локальні параметри поміщаються в стек один за одним і вибираються з стекав зворотній послідовності (латинське recurrere означає «поверненняназад »).
У Паскалі можна користуватися іменами лише тоді, коли в тексті програмицьому передує їх опис. Рекурсія є єдиним виняткомз цього правила. Назва proc можна використовувати відразу ж, не закінчивши йогоопису.
Прімер1 являє собою нескінченну рекурсію, за допомогою якої можнавстановити, наскільки великий стек. При цьому пам'ятайте, що при використаннідирективи (* $ S + *) при переповнення стека отримаємо повідомлення про помилку, а привикористанні директиви (* $ S-*) - ні, а значить, ми швидше за все зіткнемосяз зависанням системи. Установкою за умовчанням є (* $ S + *). Програмабуде перервана з видачею повідомлення про помилку "Error 202: stack overflowerror ( "Помилка 202: переповнення стека »).
Прімер1:
Program stack_test;
(програма перевірки стека) procedure proc (i: integer); begin if i mod 1024 = 0 then writeln (i: 6); proc (i +1); end;
begin proc (1); end.
Стек пов'язаний з іншою структурою пам'яті - з динамічної областю. Здопомогою директиви (* $ М *) можна керувати розміром стека.
Рекурсія не повинна сприйматися як певний програмістський трюк. Цешвидше за якийсь принцип, метод. Якщо в програмі потрібно виконати щосьповторно, можна діяти двома способами:
- За допомогою послідовного приєднання (або ітерації у формі циклу);
- За допомогою вкладення однієї операції до іншої (а саме, рекурсія).
Наступного прімере2 один раз рахунок від 1 до n ведеться за допомогою циклу, адругий - за допомогою рекурсії. При цьому добре видно, як заповнюється, апотім звільняється стек. У процедурі rekursion операція writeln (i: 30)виконується перед рекурсивним викликом, після чого writeln (i: 3) звільняєстек. Оскільки рекурсія виконується від n до 1, висновок по командіwriteln (i: 30) виконується у зворотній послідовності n, n-1, ..., 1, а висновокпо команді writeln (i: 3) - в прямій послідовності 1,2, ..., n (згідно зпринципом LIFO - останнім прийшов, першим обслужений).
Прімер2:
Показує принципове розходження між итерацией і рекурсією: ітераціїнеобхідний цикл і локальна змінна k як мінлива циклу. Рекурсіїнічого цього не потрібно!
program iterativ_zu_rekursion; var n: integer;
procedure rekursion (i: integer); begin writeln (i: 30); if i <1 then rekursion ( i-1); writeln (i: 3); end; (* Рекурсія *)
procedure schleife (i: integer); var k: integer; bagin k: = 1; while k 1 then convert (z div 8);
(* Це рекурсивний виклик *) write (z mod 8:1); end;
begin writeln ( 'Введіть деяке позитивне число:'); readln (z); writeln ( 'Десяткове число:', z: 6); write ( 'Вісімкове число:'); convert (z); end.
Один з найбільш яскравих прикладів застосування рекурсії дають числа Фібоначчі.
Вони визначаються таким чином:
x [1] = x [2] = 1 x [n] = x [n-1] + x [n-2] при n> 2 < p> Кожен елемент ряду Фібоначчі є сумою двох попередніхелементів, тобто
1 1 2 3 5 8 13 21 34 55 ...
Наступний приклад дозволяє обчислити n-ий елемент ряду Фібоначчі якІтеративний (тобто в циклі, починаючи з х [1] до х [n]), так і рекурсивно (n -ний елемент ряду є сумою двох попередніх елементів). Причомурекурсивна функція викликає себе двічі.
Прімер4:
З використанням рекурсії обчислюються числа Фібоначчі, причому глибинарекурсії індикується. Перед кожним рекурсивним викликом виводитьсявиводитися ASCII-символ із номером 8 (Backspace), а після дзвінка зновустирається. Тим самим можна спостерігати за роботою програми, оскількипрограма за рахунок delay (300) призупиняється на 0.3 с.
program fibonacci (input, output); uses crt; var n, result: integer;
function fibit (n: integer ): integer; var a, b, c, i: integer; begin a: = 1; b: = 1; if (n = 1) or (n = 2) then fibit: = 1 else begin for i = 3 to n do begin c: = a + b; a: = b; b: = c; end; fibit: = c; end; end;
begin clrscr; write ( 'n ='); readln (n); writeln ( 'Ітеративний:', fibit (n): 5); writeln ( 'рекурсивно:'); write ( '....! .... # ....! .... # ....'); writeln ( ' ! .... # ....! .... # ....! ... .#'); write ( 'Глибина рекурсії:'); result: = fibrek (n); writeln; write (result); end. < p> Цей приклад демонструє перш за все відмінності між итерацией ірекурсією. Ітерації необхідний цикл і допоміжні величини; ітераціяпорівняно ненаглядна (див. fibit в наведеному вище прикладі). Рекурсіяобходиться без допоміжних величин і звичайно простіше для розуміння, щодемонструє такий запис:
if (n = 1) or (n = 2) then fibrek: = 1 else fibrek: = fibrek (n-1) + fibrek (n-2);
Ітерація вимагає менше місця в пам'яті і машинного часу, ніж рекурсія,якої необхідні витрати на управління стеком. Отже, якщо для деякоїзавдання можливі два рішення, перевагу слід віддати ітерації. Правда,для багатьох завдань рекурсивна формулювання абсолютно прозора, в той часяк побудова ітерації виявляється досить складною справою.
Якщо процедура або функція викликає себе сама, це називають прямоюрекурсією. Але може зустрітися ситуація, коли процедура А викликаєУ процедуру, яка викликає С, а процедура З знову повертається до А. У цьомувипадки ми маємо справу справу з непрямою рекурсією, що демонструєнаведений нижче приклад. З таким типом рекурсії ми стикаємося там, девикористана директива forward.
Приклад 5:
Наступна програма видає прості числа від 1 до n, для чого використовуютьсяфункції next і prim, які викликаються перехресно, тобто рекурсивно.
Одночасно це є прикладом застосування директиви forward.
program primzahlen_rekursiv_berechnen;
(програма рекурсивного обчислення простих чисел) var n, i: integer; c: char;
function next (i: integer): integer; forward;
(Це пряме посилання вперед на функцію next, яка буде визначена пізніше)
function prim (j: integer): boolean;
(prim має значення true, якщо j просте число, і false у противному разі) var k: integer; begin k: = 2; while (k * k 0) do k: = next (k) ;
(k пробігає послідовність простих чисел, починаючи з 2, аж до кореня з j, при цьому перевіряється, чи ділиться j на одне з таких простих чисел. При цьому використовується наступна функція next) if j mod k = 0 then prim: = false else prim: = true; end (prim);
function next;
(Параметри вже стоять на засланні вперед, next обчислює, яке наступне за j просте число) var i: integer; begin
1: = i +1; while not (prim (1)) do 1: = 1 +1;
(Отже, next викликає в свою чергу prim) next: = 1; end (next); begin (******* виконувана частина програми *******) write ( ' Введіть додатне число n, '); writeln (' Повинні бути визначені все '); writeln (' попередні йому прості числа '); readln (n); for i: = 2 to n do begin if prim (i) then writeln ( i: 14) else writeln (i: 4); if i mod 23 = 0 then begin write ('': 60); read (c, c); end; end; end.
