- •Історична довідка
- •Характеристика й особливості мови
- •Алфавіт мови
- •Службові (зарезервовані) слова.
- •Структура програми мови Turbo Pascal
- •Розділ оголошень і угод
- •Розділ текстів процедур і функцій
- •Розділ основного блоку програми
- •Процедури введення-виведення. Деякі вбудовані функції Турбо-Паскаля.
- •Функції числових параметрів.
- •Базові управляючі конструкції Турбо-Паскаля Оператори умовного переходу.
- •1. Оператор if.
- •2. Оператор вибору (case)
- •Оператори циклів у Паскалі
- •1. Цикл із післяумовою (Repeat)
- •2. Цикл із предумовою (While)
- •3. Цикл із лічильником або параметром (For)
- •Концепція типів даних. Типи даних в мові Pascal
- •Дійсні типи
- •Бульовий (логічний) тип
- •Символьні і рядкові змінні
- •1. Символьний тип
- •2. Рядковий тип
- •Перерахований та обмежений типи
- •1. Перерахований тип
- •2. Обмежений тип
- •1. Поняття масиву. Одномірні масиви
- •2. Багатомірні масиви
- •3. Сортування і пошук
- •Множинний тип
- •Тип запис
- •Процедури і функції
- •Формальні і фактичні параметри. Механізм параметрів
- •Параметри - значення
- •Параметри-змінні
- •Безтипові параметри
- •Приведення типів.
- •Процедурні типи
- •Рекурсія Рекурсивні визначення
- •Рекурсивні підпрограми
- •Алгоритми з поверненням. Розв’язок задачі про рух коня
- •Алгоритми з поверненням. Розв’язок задачі про вісьмох ферзів
- •If підходить тнеn
- •Модулі в Турбо Паскалі
- •Модуль crt
- •1. Керування екраном
- •2. Робота з клавіатурою
- •3. Інші можливості
- •Графіка в Турбо Паскалі
- •1. Включення і вимикання графічного режиму.
- •2. Побудова елементарних зображень
- •3. Виведення текстової інформації.
- •Файли в мові програмування Pascal
- •Установчі і завершальні операції
- •Операції введення-виведення
- •Обробка помилок введення-виведення
- •Переміщення по файлу
- •Спеціальні операції
- •Текстові файли
- •1. Оголошення файлової змінної і прив'язка до файлу на диску
- •2. Читання даних з файлу
- •3. Запис даних у файл
- •Двійкові файли
- •1. Типізовані файли
- •2. Нетипізовані файли
- •Статичні і динамічні змінні
- •Покажчики
- •Стан покажчика
- •Установка розмірів динамічної пам'яті
- •Сумісність і перетворення посилкових типів
- •Динамічні структури даних
- •Динамічні змінні: інші види списків, стек і черга.
- •1. Інші види списків
- •2. Стек і черга
- •Дерева і пошук у деревах
- •1. Визначення й описи структур даних
- •1. Масив
- •2. Список
- •3. Дерево
- •2. Алгоритми
- •1. Лінійний пошук у масиві
- •2. Двійковий пошук
- •3. Лінійний пошук у списку
- •Змішані таблиці
- •Об’єктно-орієнтоване програмування. Що таке об’єктно-орієнтоване програмування
- •Інкапсуляція
- •Спадкування
- •Віртуальні методи і поліморфізм
- •Конструктори, динамічні об'єкти і деструктори
- •Поля і методи: сховані і загальнодоступні
- •Системно- залежні розширення
- •Налагодження змінних
- •Оверлеї
- •Переривання і системні виклики
- •Доступ до пам'яті і портів
- •Перевизначення переривань
Рекурсія Рекурсивні визначення
Визначення називається рекурсивним, якщо воно задає елементи множини за допомогою інших елементів цієї ж множини. Об'єкти, задані рекурсивним визначенням, так само називаються рекурсивними. І, нарешті, рекурсія — це використання рекурсивних визначень.
Приклад 1
Значення функції факторіал задаються виразами: 0!=1, n!=n((n-1)! Вони утворять множину {l,2,6,...}: 0!=1, 1=1-0!, 2=2-1!, 6=3-2! і т.д. Усі його елементи, крім першого, визначаються рекурсивно.
Як бачимо, функція факторіал задається рекурентним співвідношенням порядку 1 і початковим відрізком 0!=1. Узагалі, будь-яке рекурентне співвідношення порядку k разом із завданням перших елементів послідовності являє приклад рекурсивного визначення.
Приклад 2.
Арифметичні вирази з константами і знаком операцій '+' у повному дужковому записі (ПДЗ) задаються таким визначенням:
1) константа є виразом у ПДЗ;
2) якщо E і F є виразами в ПДЗ, то (E)+(F) також є вираженням у ПДЗ.
Такими виразами є, наприклад, 1, 2, (l)+(2), ((1)+ (2))+(l). Усі вони, крім констант 1 і 2, визначаються рекурсивно.
Об'єкти, визначені в прикладах 1 і 2, тобто значення функції факторіал і дужкові записи виразів, є рекурсивними.
У рекурсивному визначенні не повинно бути "замкненого кола", коли об'єкт визначається за допомогою себе самого чи за допомогою інших, але заданих через нього ж.
Приклад 3
Змінимо визначення функції факторіал на наступне: n!=n(n-1)! при n>0, 0!=1!. Спочатку значення функції від 1 виражається через її ж значення від 0, що, у свою чергу, — через значення від 1. По такому визначенню так і не довідатися, чому ж дорівнює 1!.
Приклад 4
"У попа був собака, піп її любив, вона з'їла шматок м'яса, піп її убив, у землю закопав і на камені написав, що у попа..." і т.д. ця сумна історія не має кінця, і не можна сказати, що ж саме піп написав на камені.
Приклад 5
"Де ти гроші береш?" — "У тумбочці".— "А там вони відкіля?"— "Дружина кладе".— "А в неї відкіля?"— "Я даю" — "А де ти береш?"— "У тумбочці..."
У цьому старому анекдоті не називається дійсне джерело збереження грошей. Якщо через А, В, С позначити чоловіка, його дружину і тумбочку, то переміщення грошей зображується так: A←C←B←A←... і дійсне джерело грошей залишається невідомим.
Щоб подібна "дурна нескінченність" не виникала в рекурсивному визначенні, повинні виконуватися наступні умови:
множина обумовлених об'єктів є частково впорядкованою;
кожна спадаюча по цьому упорядкуванню послідовність елементів закінчується деяким мінімальним елементом;
мінімальні елементи визначаються не рекурсивно;
не мінімальні елементи визначаються за допомогою елементів, що менше їх по цьому упорядкуванню.
Неважко переконатися, що визначення з прикладів 1, 2 задовольняють цим умовам, а з приклади 3 – 5 — ні.
Рекурсивні підпрограми
За правилами мови Паскаль, що задає область дії визначень, тіло підпрограми може містити виклики підпрограм, заголовки яких записані вище в тексті програми. Звідси випливає, що підпрограма може містити виклики самої себе — рекурсивні виклики. Виконання такого виклику нічим не відрізняється від виконання виклику будь-якої іншої підпрограми. Підпрограма з рекурсивними викликами називається рекурсивною.
Приклад 6
Напишемо рекурсивну функцію f по такому визначенню функції факторіал: n!=n (n-1)!при n>1, 1!=1(вважається, що n>0).
function f (n:integer):integer;
begin
if n=l then f:=l
else f:=n*f(n-l)
end;
При імітації виконання викликів рекурсивних підпрограм їх локальні змінні позначають у так: якщо підпрограма викликана з програми, то її локальна змінна X позначається F.X. При виконанні кожного рекурсивного виклику підпрограми F, зазначеного в її тілі, з'являється нова змінна X. Вона позначається додаванням префікса F. до позначення змінної X у попередньому виклику: F.F.X, F.F.F.X і т.п.
Приклад 7
Найбільший спільний дільник НСД(a,b) натуральних чисел a і b можна обчислити рекурсивно на підставі таких рівностей:
якщо b=0, то НСД(а, b)=a;
якщо a mod b=0, то НСД(a, b)=b;
якщо a mod b>0, то НСД(a,b)=НСД(b, a mod b).
Цьому визначенню відповідає наступна рекурсивна функція обчислення НСД:
function GCD(a,b:integer):integer;
begin
if b=0 then GCD:=a
else
if a mod b=0 then GCD:=b
else GCD:=GCD(b,a mod b)
end.
З рекурсивними підпрограмами зв'язані два важливих поняття — глибина рекурсії і загальна кількість викликів, породжених викликом рекурсивної підпрограми.
Розглянемо перше з них. У прикладі 6 приведена функція обчислення n!. Очевидно, що її виклик з аргументом, наприклад 4, закінчується лише по закінченні виклику з аргументом 3, а той у свою чергу, після виклику з аргументом 2 і т.д. Такі виклики називаються вкладеними. Таким чином, виклик з аргументом 4 породжує ще три вкладених виклики. Узагалі, при виклику цієї функції з аргументом n породжується ще n-1 виклик, і загальна кількість незакінчених викликів досягає n. У такий спосіб глибиною рекурсії виклику підпрограми називається максимальна кількість незакінчених рекурсивних викликів при виконанні її виклику.
При виконанні виклику з глибиною рекурсії m одночасно існує m екземплярів локальної пам'яті. Кожен екземпляр має визначений розмір, і якщо глибина буде надто великою, то автоматичної пам'яті, наданої процесу виконання програми, може не вистачити.
Друге поняття можна назвати загальною кількістю вкладених викликів, породжених викликом рекурсивної підпрограми. Ця кількість впливає на час виконання виклику.
Приклад 8
По властивостях трикутника Паскаля, біноміальний коефіцієнт C(m,n)=l при m≤l чи n=0, чи n=m; у противному випадку C(m, n)=C(m-l, n-l)+C(m-l, n).
Відповідно до цієї рівності напишемо рекурсивну функцію обчислення біноміального коефіцієнта C(m, n) по m, n, де 0≤n≤m:
function C(m, n:integer):integer;
begin
if (m<=l)or(n=O)or(n=m) then C:=1
else C:=C(m-l, n-l)+C(m-l, n)
end;
Як бачимо, кожен виклик, у якому значення аргументів m>l, 0<n<m, породжує два вкладених виклики. У результаті відбувається повторне обчислення тих самих величин. Наприклад, виконання виклику з аргументами (5,2) веде до того, що виклик з аргументами (3,1) виконується двічі, виклики з аргументами (2,1), (1,0) і (1,1) — тричі, а загальна кількість вкладених викликів досягає 18.
Неважко зрозуміти, що чим більше m і чим ближче n до m/2, тим більшим буде загальна кількість вкладених викликів. Ми не будемо точно визначати її залежність від аргументів. Скажемо лише, що при n=m div 2 чи n=m div 2+1 вона більше, ніж 2m/2.
Таким чином, уживання рекурсивних підпрограм вимагає обережності й уміння оцінити можливу глибину рекурсії і загальну кількість викликів. Не завжди варто писати рекурсивні підпрограми безпосередньо по рекурсивному визначенню. Принаймні, для обчислення біноміальних коефіцієнтів
Узагалі краще скористатися циклом. Справа в тім, що виконання кожного виклику підпрограми вимагає додаткових дій комп'ютера. Тому циклічний варіант опису обчислень виконується, як правило, швидше рекурсивного. Також не слід уживати рекурсію для обчислення елементів рекурентных послідовностей. При великій глибині рекурсії це взагалі може привести до вичерпання автоматичної пам'яті й аварійному завершенню програми. Ми розглядаємо лише так називану пряму рекурсію, коли підпрограма містить виклики самої себе. У програмуванні зустрічається також і непряма рекурсія, коли підпрограма містить виклики інших підпрограм, що у свою чергу містять виклики цієї підпрограми.