Зміст

Задачі

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

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

Нижче наведено приклад рекурсивної процедури, яка викликає сама себе нескінченну кількість раз і виводить на екран слово "РЕКУРС ІЯ":

Program DemoRecurs;
Procedure Print;
Begin
WriteLn('Рекурсія ');
Print;
end;
Begin
Print;
End.

При написанні рекурсивних підпрограм необхідно звертати особливу увагу на вихід із програми в потрібний момент, щоб уникнути "зациклення". Наведемо приклад рекурсивної функції, яка реалізує обчислення факторіалу від невід'ємного цілого числа n. Алгоритм будується на співвідношенні n! = (n-1)*n, що дозволяє при обчисленні факторіалу використовувати результат обчислення факторіалу попереднього числа.

Function Factorial(n:integer):longint ;
Begin
 if n=1 then Factorial:=1
 else Factorial:=n*Factorial(n-1)
End;

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

Зміст

Задачі