Рекурсивнi алгоритми. Реалізація рекурсивних алгоритмів процедурною мовою програмування

Рекурсія – спосіб звернення процедури або функції до самої себе, але із зміненими вхідними даними. Рекурсію зручно використовувати в задачах, що зводяться до розв’язання підзадач одного типу, але різної розмірності. Наприклад, обчислення факторіала числа n можна подати через звертання до обчислення факторіала числа n-1:

n!=n(n-1)!

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

Будь-яка рекурсія містить три елементи: 1) початкове значення проміжного результату (на нульовому кроці) перед початком прямого ходу; 2) спосіб одержання проміжного результату на і-му кроці прямого ходу через проміжний результат, одержаний на (і-1)-му кроці; 3) умова завершення процесу.

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

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

Function Step(x:real; n:integer):real:

Begin

If n = 0

then Step:=1

else Step:=Step(x,n-1)*x;

End;

Проаналізуємо роботу цієї функції на прикладі знаходження значення 23. При першому виклику функції значення змінних буде дорівнювати відповідно:

x = 2

n = 3.

Так як значення n не дорівнює 0 спрацює гілка else, тобто почне виконуватись такий оператор

Step:=Step(x,n-1)*x;

де x буде дорівнювати 2, і n - теж 2.

Цей оператор містить виклик функції step, тому виконання підпрограми перерветься і виконається виклик тієї ж самої функції step, але з параметрами x=2 та n=1. При виконанні повторного виклику функції ситуація повториться, так як n поки ще не дорівнює 0 і тільки на четвертому виклику функції step параметр n досягне нульового значення, після чого спрацює гілка then, яка присвоїть значення функції 1.

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

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

Модульне програмування та його реалізація в системах процедурного програмування.

Модульне програмування — парадигма програмування, основна ідея полягає в:

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

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

Якщо в деякій програмі використовуються власні процедури досить великого розміру, то ці процедури найкраще оформити в вигляді окремого модуля. Модуль – це автономно компілююча програмна одиниця, що включає в себе різні компоненти розділу описів (типи, константи, змінні, процедури і функції). По-перше, модуль може зберігатися як в вихідному виді в PAS-файлі, так і в відкомпільованому файлі з розширенням TPU (Turbo Pascal Unit - модуль ТУРБО ПАСКАЛЬ). Усі процедури не компілюються щораз при перекомпіляції основної програми, а просто їхній код, що міститься в tpu-файлі, компонується з кодом основної програми. Це значно заощаджує час загальної компіляції задачі. По-друге, винесення множини процедур в окремий модуль розвантажує текст основної програми від зайвої захаращеності, робить його більш компактним і зрозумілим для сприйняття. По-третє, модулі з процедурами, що часто зустрічаються в різноманітних програмах, заощаджують час при написанні нових програм. Для цього достатньо помістити потрібний tpu-файл в каталог із новим проектом, в основній програмі підключити цей модуль в рядку uses і далі просто використовувати процедури з цього модуля в тексті основної програми. Будова модуля нагадує створення нової програми. в окремому pas-файлі записується заголовок модуля, константи, змінні, процедури і функції, які використовуються в цьому модулеві:

Структура

Unit <ім’я>;

Interface <інтерфейсна частина>; (розділ описів)

Const глобальні_константи;

Var глобальні_змінні;

Procedure Ім’я (параметри);

Function Ім’я (параметри): тип;...

Implementation <виконуюча частина>;{розділ реалізації}

Const локальні_константи;

Var локальні_змінні;

Procedure Ім’я;...

Function Ім’я;...

Begin <ініціююча частина>;

End.

Огляд стандартних модулів

В ТР є 8 стандартних модулів: system, dos, crt, printer, graph, overlay, turbo3, graph3.

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

printer. Вивід тексту на принтер

crt. Входять процедури і функції, що забезпечують управління текстовим режимом роботи екрана. Можна переміщувати курсор в будь-яку позицію екрана, змінювати колір символів і фону.

 

 

30. Об’єктно-орієнтоване та візуальне програмування. Основні положення методології об’єктно-орієнтованого і візуального програмування. Об’єктна модель системи об’єктно-орієнтованого візуального програмування: поняття класу, властивостей класу, методів класу та їх використання в процесі реалізації взаємодії об’єктів. Інкапсуляція, успадкування, поліморфізм.