Головна

Readln (kol);

  1.  Readln (b);

...

рекурсивні підпрограми

Іноді зустрічаються такі випадки, коли задача розбивається на підзадачі, які мають ту ж структуру, що і основне завдання.

У таких випадках використовують механізм, який називається рекурсією.

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

Підпрограми, що реалізують рекурсію, називаються рекурсивними підпрограмами.

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

приклад

Обчислення факторіала числа

Обгрунтування вибору способу реалізації.

Звернемо увагу на те, що обчислити факторіал числа N можна наступним чином:

N! = N * (N-1)! = N * (N-1) * (N-2)! І так далі

Тобто для обчислення факторіала числа N потрібно обчислити факторіал числа (N-1), для обчислення факторіала (N-1) необхідно обчислити факторіал числа (N-2) і так далі. Зауважимо, що обчислення факторіала числа зводиться до обчислення факторіала числа, на одиницю менше самого числа.

Реалізуємо такий алгоритм з використанням механізму рекурсії.

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

function Fact (n: byte): integer;

Begin

if n = 0 then Fact: = 1

else Fact: = n * Fact (n-1);

End;

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

При виконанні функції Fact (n-1) згідно оператору Fact: = n * Fact (n-1), де т - параметр функції, замість n підставляється параметр (n-1) і, отже, обчислюється рядок n * (n-1) * Fact ((n-1) -1) і так далі.

Рекурсивне звернення до функції Fact триватиме до тих пір, поки n не стане рівним 0

Домашнє завдання

Реалізувати за допомогою рекурсивної підпрограми зведення числа в натуральну ступінь.

Підказка. Зауважимо, що Xn = X * Xn-1




 Мови програмування високого рівня |  Розділ 2 Програмування на алгоритмічній мові Turbo Pascal |  типи даних |  умовний оператор |  оператор переходу |  Приклад циклу типу repeat ... until |  Стандартні і призначені для користувача процедури. |  Приклад. |  Стандартні і пользоваельскіе функції |  Приклади стандартних функцій |

© 2016-2022  um.co.ua - учбові матеріали та реферати