ІНФОРМАТИКА для 9 класу


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

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

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

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

Приклад 10.3.3. Вивести текстовий рядок у зворотному порядку. Розв’язування цієї задачі виконано у вигляді рекурсивної процедури

Reverse. Використовується функція EoLn, яка повертає значення True при досягненні кінця рядка.

Procedure Reverse; var C : Char; begin

If Not Eoln then begin

Read(C); Reverse; Write(C); end;

End;

Begin Reverse; end.

У таблиці розглянуто приклад для введеного рядка ‘HELLO’.

Покрокове виконання програми

 

 

Поточний рівень рекурсії Рекурсивний спуск Рекурсивне повернення
Reverse;

EoLn=False; Введення ‘H’; Reverse; EoLn=False; Введення ‘E’; Reverse; EoLn=False; Введення ‘L’; Reverse; EoLn=False; Введення ‘L’; Reverse; EoLn=False; Введення ‘O’; Reverse;

EoLn=True;

1 Виведення ‘H’;
2 Виведення ‘E’;
3 Виведення ‘L’;
4 Виведення ‘L’;
5 Виведення ‘O’;
6

Перевіряємо себе

 

Що називається рекурсією? Рекурсивною підпрограмою? image

Де зберігаються точки виклику рекурсивної підпрограми? image

Які переваги мають програми, у яких використовуються рекурсивні підпрограми? image

Чим визначається глибина рекурсії? image

Що відбудеться, якщо не спрацює стоп-умова рекурсії або програміст її не напише? image

 

Виконуємо

Наведіть приклади застосування підпрограм із рекурсією. image

 

Напишіть програму з рекурсивною підпрограмою суми 1+2+3+…+N.

Напишіть програму з рекурсивною підпрограмою добутку 1*2*3*…*N.

Оформіть у вигляді рекурсивних процедур обчислення суми 1+2+3+…+N і добутку 1*2*3*…*N та з’ясуйте, на скільки значення добутку перевищує значення суми. image

Відсортуйте одновимірний масив за зростанням елементів, використавши рекурсивну функцію. image

image

Порівняйте швидкодію алгоритмів з використанням циклічних структур і рекурсивних підпрограм. image

image

[Всего голосов: 6    Средний: 3.5/5]

Читать  Формалізація та алгоритмізація обчислювальних процесів