7 Omzetten van Recursieve naar Iteratieve Algoritmen

B2: Algoritmiek, Datastructuren en Objectprogrammeren

Omzetten van recursie naar iteratie

7 Omzetten van Recursieve naar Iteratieve Algoritmen Het lijkt mogelijk om elke oplossings-algoritme, die vaak in eerste instantie recursief geformuleerd werd, om te zetten in een iteratieve algoritme (dus: met een of ander soort herhalingsconstructie). 1 Zo’n transformatie levert ons over het algemeen een veel moeilijker te doorgronden (en op correctheid te controleren) iteratief programma op, waarbij we veel moeite moeten besteden aan het administratieve werk van het op de goede manier bijhouden van herhalingstellertjes en hulpvariabelen. Misschien wordt door zo’n moeizame transformatie je programma lichtelijk sneller (ofschoon goede compilers daarvoor soms al zèlf op eigen houtje recursie omzetten in de corresponderende iteratie), maar erg veel maakt dat meestal niet uit en de vraag is of het de moeite van het extra werk loont. Aspecten die je kunnen dwingen om een gevonden recursieve aanpak om te zetten in een iteratieve zijn: • het niet toegestaan zijn van recursie in de te gebruiken programmeertaal (zoals: Fortran); • het ‘vol lopen’ van de stack als je te diep in recursie gaat (met té grote elementen op die stack). Het is met de bespreking van de verderop behandelde transformaties nìet de bedoeling om daarbij volledig te zijn, zelfs niet om een klakkeloos uit te voeren recept voor zo’n omzetting te geven. Kritisch nadenken en zorgvuldig controleren blijft bij elk concreet geval nodig.

7.1

Een héél eenvoudig voorbeeld ter inleiding

Het eenvoudigste zou het omzetten zijn van een parameterloze recursieve procedure. Ofschoon we zo’n parameterloze procedure nooit (of in ieder geval slechts zeer zelden) zullen gebruiken, geven we ‘for the sake of simplicity and completeness’ hier toch de benodigde transformatie: PROCEDURE Doe_recursief ; BEGIN IF conditie THEN BEGIN Doe_een_aantal_dingen ; Doe_recursief END; END ;

Deze procedure kan in principe worden herschreven in de volgende iteratieve algoritme: PROCEDURE Doe_iteratief ; BEGIN WHILE conditie DO Doe_een_aantal_dingen ; END ;

Een dergelijke parameterloze procedure zijn we sinds de tijd van ‘Kareltje’ (uit de B1-cursus) echter niet meer tegengekomen. Realistischer is het om de mogelijkheid voor zulke transformaties te gaan bekijken als er wèl een (of meer) parameters worden meegenomen. Voordat we voorbeelden van transformatie van recursie naar iteratie geven, bespreken we hier eerst in het algemeen welke vormen van recursieve aanroepen we kunnen onderscheiden (middelrecursie, rechtsrecursie…). Daarna starten we met die omzetting bij de gemakkelijkste situatie (i.e. rechtsrecursie) en geven daar een paar voorbeelden van. Daarna komt de algemene transformatie in het geval van middelrecursie (enigszins) ter sprake.

7.2

Een algemene recursieve procedure met één parameter

Zo’n algemene formulering voor een recursieve procedure-met-één-parameter kan er als volgt uitzien: PROCEDURE Doe_recursief ( x : INFO ) ; BEGIN IF geldige_conditie ( x ) THEN BEGIN

Voorbehandeling ( x ) ; Doe_recursief ( verander ( x ) ) ; Nabehandeling ( x ) END ELSE Terminatie_behandeling ( x ) END; 1

{ bij ‘stoppen’ v/d recursieve aanroepen}

Zie bijv. ‘Systematisch leren programmeren’ door professor C.H.A. Koster, deel I, blz. 243 e.v.

77



Er is in dit algemene geval (nou ja; ‘algemeen’ met één parameter) sprake van middelrecursie. Er is sprake van rechtsrecursie als de ‘nabehandeling’ ontbre ekt. N.B.

Als je wilt begrijpen waar deze termen middelrecursie en rechtsrecursie e.d. vandaan komen, kijk dan even naar het resultaat van wanneer je het code-deel tussen BEGIN en END niet ònder, maar naast elkaar zet:

Voorbehandeling ( x ) ; Doe_recursief ( Verander ( x ) ) ; Nabehandeling ( x ) en kijk of het ‘Doe_recursief’-deel in het midden of rechts of links staat.

Zoals eerder aangekondigd, bespreken we nu eerst de omzetting van rechts-recursie (zonder ‘nabehandeling’).

7.3

Het verwijderen van ‘rechts’-recursie

Bij ‘rechts’-recursie treedt dus géén nabehandeling meer op na de recursieve aanroep. We hebben dan de volgende situatie: PROCEDURE Doe_recursief ( x : INFO ) ; BEGIN IF geldige_conditie ( x ) THEN BEGIN Voorbehandeling ( x ) ; Doe_recursief ( Verander ( x ) ) END ELSE Terminatie_behandeling ( x ) END ;

{ rechtsrecursie } { uitvoeren bij ‘stoppen’ v/d recursie }

N.B. Let goed op de hierboven gebruikte formulering. De conditie bij de ‘IF’ is nìet de stopconditie, maar is de voorwaarde waarbij verder gegaan moet worden met de recursie. De plaats waar hier de ‘Terminatie_behandeling(x)’ staat is daarom dus net andersom als we tot nu toe gewend zijn (zie hoofdstukken 1, 2, 3 en 5). Als we de ‘conditie’ en de ge noemde volgorde niet goed kiezen, dan loopt de hieronder geschetste transformatie fout!

Als we een dergelijke recursieve aanpak willen omzetten naar een iteratieve aanpak, dan moeten we een hulpvariabele ‘hulp_x’ voor ‘x’ introduceren: PROCEDURE Doe_iteratief ( x : INFO ) ; VAR hulp_x : INFO ; BEGIN hulp_x := x ; WHILE geldige_conditie ( hulp_x ) DO BEGIN Voorbehandeling ( hulp_x ) ; hulp_x := Verander ( hulp_x ) END ; Terminatie_behandeling ( hulp_x ) END ;

Met, als een lichte varianten op deze geschetste transformatie, enige voorbeelden (zonder ‘vóórbehandeling’): FUNCTION Som_van_1_tot_en_met( getal: INTEGER ): INTEGER; {Recursief!} BEGIN IF getal >= 1 THEN Som_van_1_tot_en_met := getal + Som_van_1_tot_en_met ( getal - 1 ) ELSE Som_van_1_tot_en_met := 0 END ;

en de naar iteratie getransformeerde versie: FUNCTION Iteratief_Som_van_1_tot_en_met ( getal : INTEGER ) : INTEGER ; VAR hulpgetal, som_vanaf_1 : INTEGER ; BEGIN { ‘som_vanaf_1’ is nodig vanwege ‘FUNCTION’-resultaat} som_vanaf_1 := 0 ; hulpgetal := getal ; WHILE hulpgetal >= 1 DO BEGIN som_vanaf_1 := som_vanaf_1 + hulpgetal ; hulpgetal := hulpgetal - 1 ; { lees: hulp_x := Verander(hulp_x) } END ; Iteratief_Som_van_1_tot_en_met := som_vanaf_1 END ;

78



Als ander concreet voorbeeld geven we hier de transformatie van een recursieve functie voor het berekenen van de faculteitswaarde van een (geheel) getal, naar een iteratieve versie. FUNCTION Faculteit_recursief ( getal : BYTE ) : LONGINT ; BEGIN IF getal > 1 { d.w.z. ‘de conditie’ } THEN Faculteit_recursief := getal * Faculteit_recursief ( getal - 1) ELSE Faculteit_recursief := 1 { d.w.z. bij getal = 1 } END;

en de naar iteratie getransformeerde versie, waarbij we ons de vrijheid veroorloven om geen lokale hulpvariabele te gebruiken, maar gebruik te maken van de Value-eigenschappen van de parameter (waardoor we die waarde lokaal kunnen veranderen, zonder dat dit teruggespeeld wordt naar bijvoorbeeld het hoofdprogramma): FUNCTION Faculteit_iteratief ( getal : BYTE ) : LONGINT ; VAR faculteit : LONGINT ; BEGIN faculteit:= getal ; { ‘faculteit’ is nodig vanwege ‘Function’aanpak } WHILE getal > 1 DO { hier staat dus eigenlijk: WHILE conditie(..) } BEGIN getal := getal - 1 ; { dit mag; 'getal' is die Value-parameter } faculteit := getal * faculteit END ; Faculteit_iteratief := faculteit END;

Het transformeren van dit soort rechts-recursie gaat zo eenvoudig, dat sommige compilers dat al automatisch uitvoeren (omdat vaak een iteratieve aanpak toch ietsje efficiënter uitgevoerd kan worden dan een recursieve). Toch moeten we goed in de gaten houden waar we mee bezig zijn en niet klakkeloos de besproken transformatie proberen uit te voeren. Zo gaven we reeds eerder, bij de dynamische recursieve datastructuren van hoofdstuk 3, voor de recursieve ‘Toon_Lijst’ procedure voor een lineaire lijst de volgende transformatie: PROCEDURE Toon_Lijst ( wijzer : LIJSTWIJZER ) ; BEGIN IF wijzer = NIL THEN write ( ' --> NIL' ) ELSE BEGIN write ( ' --> ', wijzer^.waarde ) ; Toon_Lijst ( wijzer^.vervolg ) END; END;

{'RECURSIEVE versie'}

waarbij we al stelden, dat een iteratieve versie van deze procedure de volgende kan zijn: PROCEDURE Toon_Lijst ( wijzer : LIJSTWIJZER ); BEGIN WHILE NOT ( wijzer = NIL ) DO BEGIN write ( ' --> ', wijzer^.waarde ) ; wijzer := wijzer^.vervolg END ; writeln ( ' --> NIL' ) END ;

{‘ITERATIEVE versie'}

Bij deze ‘Toon_Lijst’-transformatie blijkt in de iteratieve vorm zelfs geen hulp-variabele nodig te zijn. Wat complexer wordt het in het volgende geval voor het bepalen van Fibonacci-getallen 2 (zie de B1-cursus) , waarbij binnen een procedure twéé recursieve aanroepen plaatsvinden (een soort dubbele rechtsrecursie dus):

2

Voor Fibonacci-getallen geldt de relatie: Fib(0) = 0 ; Fib(1) = 1 ; voor n>1 geldt: Fib(n)=Fib(n-1)+Fib(n-2).

79



FUNCTION Fibonacci_recursief ( getal : WORD ) : WORD ; BEGIN IF getal = 0 THEN Fibonacci_recursief := 0 ELSE IF getal = 1 THEN Fibonacci_recursief := 1 ELSE Fibonacci_recursief := Fibonacci_recursief (getal - 1) + Fibonacci_recursief (getal - 2) END;

Na flink wat puzzelen, is ook deze recursieve oplossing om te zetten in een iteratieve: FUNCTION Fibonacci_iteratief ( getal : WORD ) : WORD ; VAR teller, fibonnaci, fibonnaci_van_getal_min_1 : WORD ; BEGIN IF getal = 0 THEN fibonnaci := 0 ELSE BEGIN fibonnaci_van_getal_min_1 := 0 ; fibonnaci := 1 ; { beginwaarde } teller := 1 ; WHILE teller < getal DO { de iteratie } BEGIN fibonnaci := fibonnaci + fibonnaci_van_getal_min_1 ; fibonnaci_van_getal_min_1 := fibonnaci - fibonnaci_van_getal_min_1 ; inc ( teller ) END; END ; Fibonacci_iteratief := fibonnaci END;

Deze iteratieve oplossing is niet zo eenvoudig te vinden; het vereist een nieuwe analyse van het probleem van de Fibonacci-getallen en een geheel nieuwe aanpak voor het bepalen van de oplossingsalgoritme. We hebben deze beide oplossingen getoond om aan te geven, dat ook wat moeilijkere recursieve oplossingen vaak (/meestal) toch om te zetten zijn naar iteratieve oplossingen.

En dan nu een aanzet voor het algemene geval: de omzetting van middelrecursie.

7.4

Het verwijderen van middelrecursie

We zagen reeds de volgende algemene formulering van een recursieve procedure met één parameter: PROCEDURE Doe_recursief ( x : INFO ) ; BEGIN IF geldige_conditie ( x ) THEN BEGIN

Voorbehandeling ( x ) ; Doe_recursief ( verander ( x ) ) ; Nabehandeling ( x ) END ELSE Terminatie_behandeling ( x ) END;

In het algemeen geldt dat we voor het omzetten van middelrecursie naar iteratie een ‘LiFo-stack’ (LiFo: Last in First out) nodig hebben. In bovenstaande ‘doe_recursief’-procedure kunnen we zien, dat de ‘voorbehandeling’ met een bepaalde waarde van ‘x’ gebeurt en dat diezelfde waarde van ‘x’ ook gebruikt moet worden om -na terugkomst uit recursie- de ‘nabehandeling’ te laten uitvoeren. Bij omzetting naar een iteratieve vorm zullen we ná de voorbehandeling de op dat moment bestaande waarde van ‘x’ op een stack moeten ‘push’-en om die later voor de ‘nabehandeling’ weer te voorschijn te ‘ pop’-pen. Op een dergelijke wijze is bijvoorbeeld onze recursieve quicksort-procedure om te zetten naar een iteratieve variant.

80



We geven hier eerst een algemene aanpak van zo’n transformatie (in de taal Elan (van: Educational Language)): PROC recursieve procedure(INFO CONST x): IF geldige conditie(x) THEN voorbehandeling(x); recursieve procedure(verander(x)); { middelrecursie dus! } nabehandeling(x) ELSE terminatie behandeling(x) FI; ENDPROC;

Omzetten naar ITERATIE: We hebben een LiFo-stack nodig, waar de ‘push’ en ‘pop’ op werken: PROC iteratieve procedure(INFO CONST x): INFO VAR x1 :: x; WHILE geldige conditie(x1) REP voorbehandeling(x1); push(x1); x1 := verander(x1); ENDREP; terminatie behandeling(x1); WHILE pop(x1) REP nabehandeling(x1) ENDREP; ENDPROC;

7.4.1 Definitie/declaratie en gebruik van de stack De vorm die aan die benodigde stack wordt gegeven (een rij, een dynamische lineaire lijst etc.) hangt af van het concrete geval. We declareren hier een stack (als een Elan-ROW ): LET max = groot genoeg; ROW max INFO VAR stack; INT VAR top :: 0;

Hulpprocedure ‘push’ om een element op de stack te plaatsen:

Hulpprocedure ‘pop’ om een element van de stack te halen: BOOL PROC pop(INFO VAR x): IF top >= 1 THEN x := stack[top]; top DECR 1; TRUE ELSE FALSE FI; ENDPROC;

PROC push(INFO CONST x): top INCR 1; stack[top] := x; ENDPROC;

7.4.2 Een robuustere versie: We moeten er bij een robuustere versie rekening mee houden, dat de stack weleens zou kunnen ‘vol lopen’ en er (via push) geen volgend element meer bij kan, of ‘leeg’ zou zijn , terwijl we er een element van terug willen halen. PROC iteratieve procedure (INFO CONST x): INFO VAR x1 :: x; WHILE geldige conditie(x1) REP voorbehandeling(x1); IF NOT push(x1) THEN stop; x1 := verander(x1); ENDREP; terminatie behandeling(x1); WHILE pop(x1) REP nabehandeling(x1) ENDREP; ENDPROC;

81



BOOL PROC push (INFO CONST x): top INCR 1; IF top <= max THEN stack[top] := x; TRUE ELSE FALSE; ENDPROC;

7.4.3 Voorbeeld: print getal. We geven hier (in de Elan-versie) de in het eerste hoofdstuk over recursie besproken procedure voor het (ietwat moeizaam…) recursief tonen/afdrukken van een getal. PROC print getal ( INT CONST n ): Recursief: IF n >= 10 THEN print getal ( n DIV 10 ); print cijfer( n MOD 10 ) ELSE print cijfer( n ) FI; ENDPROC;

Iteratief met Stack:

{ ‘linksrecursie’ }

PROC print getal ( INT CONST n ): INT VAR n1 :: n; WHILE n1 >= 10 REP push ( n1 ); n1 := n1 DIV 10 ENDREP; print cijfer ( n1 ); WHILE pop ( n1 ) REP print cijfer ( n1 MOD 10 ) ENDREP ENDPROC print getal;

De rest van het Elan-programma: LET INFO = INT; LET stack max = 12; PROC print getal ( INT CONST n ): INT VAR n1 :: n; WHILE n1 >= 10 REP push ( n1 ); n1 := n1 DIV 10 ENDREP; print cijfer ( n1 ); WHILE pop ( n1 ) REP print cijfer ( n1 MOD 10 ) ENDREP ENDPROC print getal;

PROC print cijfer ( INT CONST c ): put ( "0123456789" SUB c + 1 ) ENDPROC print cijfer; program: ROW stack max INFO VAR stack; INT VAR top :: 0; print getal ( 12345 ).

Tot slot herhalen we hier de in het begin van dit hoofdstuk gemaakte opmerking, dat het omzetten van recursie in iteratie meestal qua efficiëntie niet zoveel uitmaakt en dat het de grote vraag is, of het het extra werk loont. En bovendien: een groot voordeel van een recursieve formulering is, dat die (meestal) inzichtelijk is en dat de correctheid ervan relatief gemakkelijk is na te gaan. Waarom zou je dan die correctheid in gevaar brengen door per se een transformatie naar een iteratieve formulering te willen doorvoeren. Doe zo’n transformatie daarom alleen als dat echt nodig is.

82

7 Omzetten van Recursieve naar Iteratieve Algoritmen

Recommend Documents