ALG5

6.6. Klasyczne schematy derekursywacji 185

Sprawdźmy teraz, czy w istocie podane wyżej przekształcenie działa. W tym celu powróćmy do programu przykładowego ze strony 179 (zapisanego teraz w nieco zwięźlejszej postaci).

odwroH.cpp

void P2()

(

if (a!=0)

I

a—;

P2();

b=b+ (++a);

1

ei.se

b=l;

)

Stosując omawiane przekształcenie otrzymujemy natychmiast:

void P?_TTF.RAT()

{

int k=0;

while (a!=0)

i

a—; k++;

)

while(k—!0) h>=b+ (++a) ; i

Wykonanie programu potwierdza równoważność obu procedur.

6.6.3.Schemat z podwójnym wywołaniem rekurencyjnym

Ostatni omawiany schemat rekurencyjny należy do tzadko spotykanych w praktyce. Ponadto dowód na poprawność transformacji jest dość złożony, dlatego poniżej przeanalizujemy jedynie gotowy rezultat i omówimy przykład zastosowania transformacji.

Oto dwie rówmoważne formy algorytmów:

void P()

{

if(warunek (x)) <

A (x) ;

PO;

B (x) ;

PO;

C(x) ;

)

else

int N=l; void P()

(

do

{

while(warunek(x)) (

A (x > ;

N*=2;

)

Olx) ;