Lineare Rekursion

{ x = A }

s := Empty ;

while not P(x) do { p(f(x),s) = f(A) }

s := push(x,s) ;

x := r(x) ;

z := g(x) ;

while s <> Empty do { p(z,s) = f(A) }

z := h(z,top(s)) ;

s := pop(s)

{ x=f (A) }

begin and enddurch Einrücken ersetzt

p(x, Empty) = x

p(x, push(y,s)) = p(h(x,y),s)

Korrekt gdw. eine Funktion

p existiert mit:

Ein iteratives Programm für f benutzt einen Stack.

Allgemeine Form einer linearl rekursiven Funktion f.

Vorherige Folie

Nächste Folie

Zurück zur ersten Folie

Graphik-Version anzeigen