Rekursja pośrednia

Rekursja pośrednia to taka rekursja, w której jednocześnie jest definiowanych kilka (tzn. więcej niż jeden) obiektów, które nawzajem „z siebie korzystają”.

Przykład

Obliczamy wartości funkcji $s(x)$ i $c(x),$ które są przybliżeniami odpowiednio funkcji sinus i cosinus w sposób następujący:

• sposób na wyliczanie $s(x){:}$
  • jeśli zachodzi warunek: $|x|<a$ to za wartość $s(x)$ wstaw $x;$
  • w przeciwnym wypadku za $s(x)$ wstaw wartość wyrażenia $2*s(x/2)*c(x/2).$

• sposób na wyliczanie $c(x){:}$
  • jeśli zachodzi warunek: $|x|<a$ to za wartość $c(x)$ wstaw 1;
  • w przeciwnym wypadku za $c(x)$ wstaw wartość wyrażenia $c^{2}(x/2)-s^{2}(x/2).$

Stała $a$ jest arbitralnie wybraną „małą” liczbą (od jej wielkości zależy dokładność przybliżenia). Zauważmy, że do wyliczenia wartości funkcji $s(x)$ potrzebna jest nam znajomość wartości funkcji $c(x/2)$ i odwrotnie.