Рекурсивний називається об’єкт, частково складається або визначається за допомогою самого себе. Факторіал – це класичний приклад рекурсивного об’єкта. Факторіал числа п – це твір цілих чисел від 1 до п. Позначається факторіал числа п так: n !.
Згідно з визначенням
n! = 1 х 2 х 3 х … х (п – 1) х п . наведене вираз можна переписати так:
n! = Nх ((n – 1) х (n – 2) х … х 3 х 2 х 1) = n х (n – 1)!
Тобто, факторіал числа п дорівнює добутку числа п на факторіал числа (п – 1). В свою чергу, факторіал числа (& laquo; -!) – це добуток кількості (п – 1) на факторіал числа (П – 2) і т. Д.
Таким чином, якщо обчислення факторіала п реалізувати як функцію, то в тілі цієї функції буде інструкція виклику функції обчислення факторіала числа (п – 1), т. е. функція викликатиме сама себе. Такий спосіб виклику називається рекурсією, а функція, яка звертається сама до себе, називається рекурсивної функцією.
У лістингу 12.1 приведена рекурсивна функція обчислення факторіала.
Лістинг 12.1. Рекурсивна функція обчислення факторіала
function factorial (n: integer): integer; begin if n <> 1 then factorials n * factorial (n-1) // функція викликає сама себе else factorial: = 1; // рекурсивний процес закінчений end;
Зверніть увагу, що функція викликає сама себе тільки в тому випадку, якщо значення отриманого параметра k не дорівнює одиниці. Якщо значення параметра дорівнює одиниці, то функція сама себе не викликає, а повертає значення, і рекурсивний процес завершується.
На рис. 12.1 наведено вид діалогового вікна програми, яка для обчислення факторіала числа використовує рекурсивную функцію factorial. Текст програми приведений в лістингу 12.2.
Рис. 12.1. Вікно програми обчислення факторіала
Лістинг 12.2. Використання рекурсивної функції
unit factor;
interface
uses
Windows, Messages, SysUtils, Classes,
Graphics, Controls, Forms, Dialogs, StdCtrls;
type
TForm1 = class (TForm)
Label1: TLabel;
Edit1: TEdit;
Button1: TButton;
Label2: TLabel;
procedure ButtonlClick (Sender: TObject);
private
{ Private declarations} public
{ Public declarations} end;
var
Form1: TForm1;
implementation
{$ R * .DFM}
// рекурсивна функція
function factorial (n: integer): integer;
begin
if n > 1
then factorial: = n * factorial (n-1) // функція викликає сама себе
else factorial: = 1; // факторіал 1 дорівнює 1
end;
procedure TForml.ButtonlClick (Sender: TObject);
var
k: integer; // число, факторіал якого треба вирахувати
f: integer; // значення факторіала числа k
begin
k : = StrToInt (Edit1.Text);
f : = Factorial (k);
label2.caption: = 'Факторіал числа '+ Edit1.Text
+ 'Дорівнює' + IntToStr (f);
end;
end.
На рис. 12.2 наведені два діалогових вікна. Результат обчислення факторіала, представлений на рис. 12.2, а, відповідає очікуваному.
Рис. 12.2. Приклади роботи програми обчислення факторіала
Результат, представлений на рис. 12.2, б, не відповідає очікуваному. Факторіал числа 44 дорівнює нулю! Сталося це тому, що факторіал числа 44 настільки великий, що перевищив максимальне значення для змінної типу integer, і, як кажуть програмісти, відбулося переповнення з втратою значення.
Delphi може включити в виконувану програму інструкції контролю діапазону значень змінних. щоб інструкції контролю були додані в програму, потрібно у вкладці Compiler діалогового вікна Project Options (рис. 12.3) встановити прапорець Overflow checking (Контроль переповнення), який знаходиться в групі Runtime errors (Помилки часу виконання).
Рис. 12.3. Вкладка Compiler діалогового вікна Project Options