Teorija

Savstarpēja rekursija un komanda "forward"
Savstarpēja rekursija ir situācija, piemēram, kad viena funkcija izsauc otru funkciju, bet tā savukārt pirmo.
 
Lūk vienkāršs piemērs.
\( f(x) = \begin{cases} 0, & \text{ja } n \leq 0 \\ f_{n-1} + g_{n-1}, & \text{ja } n > 1 \end{cases} \)
un
\( g(x) = \begin{cases} 0, & \text{ja } n \leq 0 \\ f_{n-1} + g_{n-1} + 1, & \text{ja } n > 1 \end{cases} \)
 
Kad šīs divas funkcijas mēģina uzrakstīt Turbo Pascal, parādās problēma - izsaukt var tikai funkciju, kas ir jau iepriekš ieviesta. Bet, lai kuru funkciju ņemtu kā pirmo, pirms tās noteikti jāievieš otrā, kas vēl nemaz neeksistē.
 
Šādu problēmu atrisināšanai jāizmanto "forward" komanda, kas ļauj paziņot par funkcijas vai procedūras esamību, bet tās saturu ar visām tajā esošajām darbībām uzrakstīt jau daudz tālāk programmas kodā.
 
Tas izskatās šādi.
 
Program MutualRecursion;
  
function f(n: integer): integer; forward;
  
function g(n: integer): integer;
begin
    if (n <= 0)
        then g := 1
        else g := f(n-1) + g(n-1) + 1;
end;
  
function f(n: integer): integer;
begin
    if (n <= 0)
        then f := 0
        else f := f(n-1) + g(n-1);
end;
  
begin
  writeln(f(10), ' ', g(10));
end.
 
P.S. Ja ir interese, var papētīt, kādas ir funkciju f un g vērtības ar dažādiem argumentiem un atrast likumsakarību. Un varbūt pat pierādīt to!