вона сама. Якщо в процедурі не використовуються глобальні змінні, то це також необхідно, щоб рекурсія НЕ тривала до нескінченності. br/>
. Складна рекурсія
Можлива трохи складніша схема: функція A викликає функцію B, а та в свою чергу викликає A. Це називається складною рекурсією. При цьому виявляється, що описувана першої процедура повинна викликати ще описану. Щоб це було можливо, потрібно використовувати випереджувальний опис <# "9" height = "7" src = "doc_zip8.jpg"/>, то його остання цифра в його двійковому поданні дорівнює
.
Взявши ж цілу частину від ділення на 2:
,
отримаємо число, що має той же двійкове подання, але без останньої цифри. Таким чином, досить повторювати наведені дві операції поки поле чергового поділу не отримаємо цілу частину рівну 0. Без рекурсії це буде виглядати так:
x> 0 do
begin
c: = x mod 2;
x: = x div 2; (c);
end;
Проблема тут в тому, що цифри двійкового подання обчислюються у зворотному порядку (спочатку останні). Щоб надрукувати число в нормальному вигляді доведеться запам'ятати всі цифри в елементах масиву і виводити в окремому циклі. p> За допомогою рекурсії неважко домогтися виведення в правильному порядку без масиву і другого циклу. А саме:
BinaryRepresentation (x: integer);, x: integer;
{Перший блок. Виконується в порядку виклику процедур}
c: = x mod 2;: = x div 2;
{Рекурсивний виклик} x> 0 then (x);
{Другий блок. Виконується в зворотному порядку} (c);;
Взагалі кажучи, ніякого виграшу ми не отримали. Цифри двійкового подання зберігаються в локальних змінних, які свої для кожного працюючого примірника рекурсивної процедури. Тобто, пам'ять заощадити не вдалося. Навіть навпаки, витрачаємо зайву пам'ять на зберігання багатьох локальних змінних x. Тим не менш, таке рішення є найбільш прийнятним. br/>
. Рекурентні співвідношення. Рекурсія і ітерація
Кажуть, що послідовність векторів задана рекурентним співвідношенням, якщо задано початковий вектор і функціональна залежність подальшого вектора від попереднього
В
Простим прикладом величини, що обчислюється за допомогою рекурентних співвідношень, є факторіал
В
Черговий факторіал можна обчислити за попереднім як:
В
Ввівши позначення, отримаємо співвідношення:
В
Вектора з формули (1) можна інтерпретувати як набори значень змінних. Тоді обчислення необхідного елемента послідовності складатиметься в повторюваному оновленні їх значень. Зокрема для факторіала:
: = 1;
for i: = 2 to n do
x: = x * i; (x);
Кожне таке оновлення (x: = x * i) називається итерацией, а процес повторення ітерацій - ітерірованіем.
Звернемо, проте, увагу, що співвідношення (1) є чисто рекурсивним визначе...
