12. Recursie

Een functie mag een andere functie aanroepen. Maar wat gebeurt er als een functie zichzelf aanroept? In dit geval spreek je van recursie of in zichzelf terugkerende herhaling. Recursie is een handige en krachtige methode van programmeren. Je hoeft eigenlijk maar 1 functie te schrijven die dan de rest van het werk doet door zichzelf aan te roepen. Na deze aanroep zijn er 2 functies actief. De tweede functie roept weer zichzelf aan. Waarna er 3 functies actief zijn. De derde functie roept zichzelf weer aan enzovoort. In het plaatje hieronder zie je een voorbeeld van recursie. Belangrijk bij recursie is dat er wel een stopvoorwaarde is, anders gaat het programma oneindig door.

Een voorbeeld:

#include <bits/stdc++.h>
using namespace std;
 
void telRecursief(int getal) {
  if (getal > 0){
    telRecursief(getal-1);
  }
  cout << getal << endl;  
}
 
int main(){
  telRecursief(5);
  return 0;            
}

In dit voorbeeld is de stopconditie wanneer getal de waarde 0 heeft.

Een tweede voorbeeld waar we naar gaan kijken is de reeks van Fibonacci. Dit is een van de beroemdste getallenreeksen in de wiskunde. De rij van Fibonacci is een reeks van getallen waarbij ieder getal in deze reeks de som is van de 2 voorgaande getallen. De eerste 2 getallen van de Fibonacci reeks zijn 0 en 1. Het begin van de Fibonacci reeks is: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, etc.

Hieronder staat de code om het het n-de Fibonacci getal te berekenen. In dit geval het zesde.

#include <bits/stdc++.h>
using namespace std;
 
int fib(int n)
{
    // Stopconditie
    if (n == 1 || n == 2){
        return 1;
    }
    // Recursieve aanroep
    int f1 = fib(n - 1);
    int f2 = fib(n - 2)
    return  f1 + f2;
}
 
int main(){
  cout << fib(6);
  return 0;            
}

Zoals ziet wordt in deze functie de functie fib op twee verschillende manier recursief aangeroepen, een keer met fib(n-1) en een keer met fib(n-2). In de boom hieronder zie alle functie aanroepen die gedaan worden:

Het diagram hierboven noemen we een boom. De boom is hierbij ondersteboven getekend: het vakje waarin het cijfer Fib(6) staat, is de wortel van de boom. De vakjes waarin de cijfers Fib(2) en Fib(1) staan, zijn twee van de bladeren van de boom.

De volgorde waarin de boom doorlopen wordt, kan je zien aan de grijze nummers in het plaatje hierboven.

• We beginnen altijd bij de wortel van de boom (bij bolletje 1), in dit geval Fib(6)

• Daarna wordt fib(n-1) aangeroepen net zolang totdat de stopconditie is bereikt, dit is het geval bij bolletje 5. In dit geval wordt 1 teruggeven en een stap teruggegaan in de boom. En wordt fib(n-2) aangeroepen, je komt dan bij bolletje 6.

• Ook bij bolletje 6 is de stopconditie bereikt en wordt ook 1 teruggeven en een stap teruggegaan in de boom.

• Bij bolletje 4 kan nu Fib(3) berekent worden. Dit is de som van f1 (=bolletje 5) + f2 (=bolletje 6), en die is in dit geval 1+1 =2.

• En zo wordt de hele boom doorlopen. Er wordt altijd eerst fib(n-1) aangeroepen totdat de stopconditie is bereikt dan wordt fib(n-2) aangeroepen totdat de stopconditie is bereikt, daarna worden f1 + f2 opgeteld.

• Bereken zelf de uitkomst van Fib(5) (Bij bolletje 2)

• Bereken zelf de uitkomst van Fib(4) (Bij bolletje 11)

• En kan je ook de uitkomst berekenen van Fib(6)?

Opdrachten recursie:

1. Wat gebeurt er als je bovenstaande code zonder stopconditie runt?

2. Schrijf een recursief programma dat terugtelt van getal tot 1.

3. Schrijf een recursief programma dat kan machtsverheffen. Voorbeeld invoer: 3 4 Voorbeeld uitvoer: 81

4. Palindromen zijn woorden die symmetrisch zijn. Ze kunnen zowel van voren naar achteren als andersom worden gelezen. Voorbeelden zijn lepel, parterretrap en meetsysteem. Schrijf een recursief programma dat bepaalt of een woord een palindroom is of niet. Het idee van de recursieve code is:

   • Als de string maar uit 0 of 1 letter bestaat dan is dit een palindroom

   • Anders vergelijk de eerste en de laatste letter van de string

     • Als de eerste en laatste letter niet gelijk zijn dan is de string geen palindroom

     • Als de eerste en laatste letter gelijk zijn dan roep deze code weer opnieuw aan met de overgebleven substring

5. Schrijf het programma Grootste Gemene Deler uit het hoofdstuk Functies - deel 1 nog een keer maar nu recursief. Met de volgende link kan je testen of je programma werkt: GGD inleveren.

Quicksort

Quicksort is een methode om getallen te sorteren. Bij deze methode worden niet alle elementen afzonderlijk met elkaar vergeleken, maar wordt de rij in steeds in tweeën verdeeld totdat dit niet meer mogelijk is. Het verdelen van de rij in tweeën gebeurd als volgt: - kies een pivot. De pivot kan het eerste getal uit de rij zijn maar ook het laatste of middelste getal. Noem dit getal x. - Zet alle elementen van de rij die kleiner zijn dan x, links van x, en zet alle getallen die groter zijn dan x, rechts van x. Laat daarna dezelfde stappen recursief los op de getallen die links van x staan, en ook op alle getallen die rechts van x staan.

Opdracht 6 - Teken op papier een voorbeeld rij getallen en sorteer de getallen met quicksort op papier. - Schrijf een recursief programma dat een rij getallen met de Quick sort methode sorteert. - Welk sorteer algoritme gebruikt de built-in functie sort()?