Recursie in programma's

We starten eenvoudig met een recursief algoritme op papier.

Hieronder staat de hoofdlijn van een algoritme voor het sorteren van een lijst getallen

Haal het kleinste getal uit de lijst en zet die vooraan

Sorteer de rest van de lijst

 

Goed, de eerste regel is een deeltaak (functie) die nog verder uitgewerkt moet worden, maar die is zeker veel eenvoudiger dan het complete sorteeralgoritme. Je ziet ook de recursie: het sorteeralgoritme roept zichzelf aan, op een deel van de lijst.

Het ziet er redelijk simpel uit, maar het werkt. Het plaatje hieronder laat dat zien.

De recursie moet wel een keer stoppen

Nu klopt het plaatje niet helemaal met het algoritme. In het plaatje stoppen we gewoon als de lijst 'op' is, maar dat staat niet in het algoritme. Dat zal gewoon proberen door te gaan en de kleinste te vinden in een lijst zonder iets. Om het goed te doen moeten we het algoritme aanpassen:

Als er in de rest van de lijst nog iets over is

{    

     Haal het kleinste getal uit de lijst en zet die vooraan

     Sorteer de rest van de lijst

}

 

Hier zie je het tweede belangrijke element van de recursie. Recursie gaat in principe gewoon door met het aanroepen van zichzelf. Dat wordt dan een oneindige lus. Je hebt dus een voorwaarde nodig om de recursie door te laten lopen, als die niet meer waar is, stopt het. Dat is hier als de lijst 'op' is.