Проектування рекурсії та ітерації

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

 

Рекурсія - це такий спосіб організації обробки даних, за якого програма викликає сама себе безпосередньо, або за допомогою інших програм.

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

Будь-який алгоритм, реалізований у рекурсивної формі, може бути переписаний у ітераційному вигляді, і навпаки.

Продовжимо дослідження застосування рекурсії, звертаючи особливу увагу на процес побудови програми і доведення її правильності. Рекурсивна програма зазвичай виникає, як результат рекурсивного обчислення певної функції на множині програмних змінних, а доведення її правильності вимагає дослідження двох питань:
1) чи завжди і чому програма закінчує роботу?
2) чому після закінчення роботи програми буде отримано потрібний результат?

Розглянемо таку задачу.

ЗАВДАННЯ 9.22. Напишіть рекурсивну програму, яка перемножує два цілих числа, одне з яких невід’ємне, без використання операції множення. Точні перед- і постумови цієї програми такі: Числа програмі змінювати не можна. Часова складність програми не повинна перевершувати

Розв’язок. Фіксуючи a, розглянемо функцію , яка задається наступним рекурсивним визначенням:
,
, коли b позитивно і парне,

, коли b позитивно і парне.

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

Текст програми:

public class MulR { static int mul(int x, int y) { // Xterm.print(" Вызов mul(" + x + "," + y + ")\n"); return (y == 0)? 0: ((y&1) == 0)? mul(x,y >>> 1) << 1: mul(x,y-1) + x; } public static void main(String[] args) throws Exception { int a = Xterm.inputInt("a -> "); int b = Xterm.inputInt("b -> "); Xterm.println("a * b = " + mul(a,b)); }}

Ця програма закінчує роботу, оскільки кожен наступний рекурсивний виклик зменшує значення аргументу y функції не менше, ніж на одиницю (непарне число зменшується рівно на один, а парне -- ділиться навпіл, що при y = 2 приводить до зменшення на один, а при великих значеннях y -- до більшого зменшення). В результаті кінцевого числа таких операцій y гарантовано стане нулем, що приведе до завершення ланцюжка рекурсивних викликів.... Зверніть увагу на той факт, що хоча наведені вище міркування не є справедливими при негативних значеннях числа b, це не означає неправильність програми, тому що відповідно до специфікації її поведінка за умови b може бути довільною.

Доведення правильності одержуваного результату проведемо за допомогою методу математичної індукції, показавши, що при фіксованому a та 0 є тавтологією предикат = (дана програма друкує ).

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

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

Якщо число є непарним, то .

Обгрунтування цих рівностей проводиться аналогічно.

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

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

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

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

Розглянемо ще одну задачу.

 

ЗАВДАННЯ 9.23. Напишіть програму, яка друкує значення багаточлена степеню в заданій точці . Коефіцієнти багаточлена зберігаються в масиві за порядком зменшення ступенів і є цілими числами, також як і значення . Величини n, та елементи масиву а змінювати в програмі неможна.

 

Рішення. Зауважимо, що

, де

,

Скориставшись цим, визначимо функцію наступним чином:

,

, при .

Тепер можна написати програму, яка реалізовує обчислення цієї функції.

 

Текст програми:

public class PolVal { static int a[], x0; static int pol(int k) { return (k == 0)? a[0]: x0 * pol(k-1) + a[k]; } public static void main(String[] args) throws Exception { int n = Xterm.inputInt("n -> "); a = new int[n+1]; for (int i=0; i<=n; i++) a[i] = Xterm.inputInt("a[" + i + "] -> "); x0 = Xterm.inputInt("x0 -> "); Xterm.println("P(" + x0 + ") = " + pol(n)); }}

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

 

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

Рекурсивне рішення задачі часто є менш ефективним, ніж еквівалентна йому за іншими параметрами ітераційне рішення. Звичайним способом програмної реалізації ітерації є цикл, і тому ми будемо вважати, що специфікація завдання на ітерацію має вигляд {Q} "S0; while (e) S;" {R}.

 

 

.

Рис. 9.1. Структура математичної моделі ітерації

Розглянемо X - множину значень всіх програмних змінних (прямий добуток множин значень окремих змінних), його підмножини і , зумовлені предикатами Q і R, і перетворення T: X → X, відповідне разовому виконанню тіла циклу S.

Тоді побудова умови продовження циклу e і його тіла S зводиться до знаходження предиката e і такого перетворення, що

Саме цей факт є основним результатом, що випливає з визначення найслабшої передумови wp для оператора циклу. Геометрична інтерпретація математичної моделі ітерації, що зводиться до багаторазового застосування перетворення T, наведена на рисунку 9.1.

На жаль ця математична модель ітерації є занадто загальною і важко застосовною на практиці, так як вона не дає конкретних рекомендацій по знаходженню умови продовження циклу і тіла циклу S за заданими Q і R. До розгляду більш часткових і більше корисних схем ми зараз і перейдемо.