Teorija

Rekursīvas funkcijas definīcija un piemērs
Rekursīva funkcija satur
1) apstāšanās gadījumus, kuros funkcijas vērtību var aprēķināt uzreiz,
2) gadījumus, kuros funkcija izsauc pati sevi.
Svarīgi!
Lai rekursīva funkcija nedarbotos bezgalīgi, ir jānodrošina, lai ar jebkurām pieļaujamām argumenta vērtībām tā noteikti sasniegtu apstāšanās gadījumus un vairs neizsauktu pati sevi.
 
Piemēram, faktoriālu \( n! = 1\cdot 2 \cdot ... \cdot n \) (un \( 0! = 1 \)) var aprēķināt šādā rekursīvā veidā:
\( 0! = 1 \\ n! = n \cdot (n-1)! \)
 
\( 0! = 1\) ir gadījums, kurā faktoriāla vērtība ir zināma uzreiz. Savukārt formula \(n! = n \cdot (n-1)!\) atbilst gadījumiem, kuros funkcija izsauc pati sevi. Katrā tādā reizē \(n\) paliek aizvien mazāks un pie nulles apstājas, tāpēc skaidrs, ka šādi var aprēķināt jebkura nenegatīva skaitļa faktoriālu.
 
Lūk faktoriāla aprēķināšanas funkcija, kas atbilst šim rekursīvajam aprakstam.
 
function fact(n: integer): integer;
begin
    if n = 0 then fact := 1;
    if n > 0 then fact := n * fact(n-1);
end;