Practicum Proefstuderen: Recursie

Introductie

Ter herinnering: we noemen iets recursief als het naar zichzelf verwijst. Dit is nog behoorlijk vaag. Om recursie echt te kunnen gebruiken voor het oplossen van problemen zullen we iets preciezer moeten zijn.

Voorbeeld 1. Een hond is een dier dat afstamt van een hond.

We kunnen hieruit niet afleiden wat een hond is, omdat hier in feite sprake is van een cirkelredenering. Je verwijst echt letterlijk naar jezelf.

Om een probleem te kunnen oplossen moet je verwijzen naar kleinere/eenvoudiger versies van jezelf.

Voorbeeld 2. (zie ook het college) Je kunt iemands leeftijd berekenen volgens deze recursieve formulering:

leeftijd (nu) = leeftijd (1 jaar geleden) + 1

Dit werkt al beter dan het vorige voorbeeld, maar geeft nog geen oplossing. Er is hier sprake van eeuwige recursie: leeftijd(2014) = leeftijd(2013) + 1 = leeftijd(2012) + 1 + 1 = leeftijd (2011) + 1 + 1 + 1 = ...... Je zult zo eeuwig doorgaan. Om je leeftijd te kunnen berekenen met bovenstaande recursieve methode zul je moeten zorgen dat de recursie stopt: de leeftijd in je geboortejaar was 0. In dit geval is de stopconditie bijvoorbeeld: leeftijd (1996) = 0; Met behulp van de recursieve formulering vind je dan: leeftijd (2014) = 18. Probleem opgelost.

De algemene vorm van een recursief algoritme is

   if (basisgeval) then
      makkelijk;
   else
      recursieve aanroep(en) naar eenvoudiger/kleiner geval(len);

Optellen

\( \mathit{Som}(n) = \mathit{Som}(n-1) + n\)

We hebben de oplossing recursief geformuleerd: \(\mathit{Som}(n)\) verwijst naar kleinere/eenvoudiger versies van zichzelf (namelijk \(\mathit{Som}(n-1)\)). Echter, we moeten nog zorgen dat we een stopconditie hebben, waardoor de recursie daadwerkelijk stopt. Merk op dat we \( \mathit{Som} \) "aanroepen" voor steeds kleinere waarden van \(n\). Op een gegeven moment zal \(n\) de waarde 1 hebben; in dat geval valt er niets meer op te tellen. We kunnen dit geval dus als stopconditie nemen: de som van alleen het getal 1 is 1.

#include <iostream>
using namespace std;

int Som(int n) {
   if (n == 1)
      return 1;
   else
      return Som(n-1) + n;
} // Som

// hier het *hoofdprogramma*  (verplicht in C++)
int main ( ) {
   int getal = 12345;
   cout << "De som van de getallen 1 t/m " << getal
        << " is: " << Som(getal)  << endl;
   return 0;
} // main

Opdracht. Lees het programma en probeer de verschillende onderdelen te herkennen. We gaan nu ook controleren dat het inderdaad werkt. We geven hieronder instructies hoe je het programma kunt uitvoeren op de computer.

Let op: In C++ is de gelijkheidstest "a==b" maar voor de toekenning van waarde b aan a gebruik je een enkel gelijk-teken "a=b": a wordt gelijk aan (de waarde van) b.

Programmeren

Open een terminal (een venster om commando's (instructies) te geven). Dit kan met de toetscombinatie Ctrl-Alt-T. Misschien moet je in de terminal het commando change directory cd uitvoeren om op de juiste plek, je home directory, uit te komen. Geef steeds enter " ⏎" na een instructie.

cd

gedit mijnsom.cc &

Een programma geschreven in C++ moet je eerst compileren (en linken) voordat je het kunt draaien. Als er fouten zijn krijg je daarover na het compileren een melding. Code verbeteren, file opslaan, opnieuw compileren en runnen. Compileren en runnen doe je met de eerste twee commando's hieronder.

g++ -Wall -O2 -o som mijnsom.cc
./som
ls -lrt

gedit mijnsom.cc &

g++ -Wall -o som mijnsom.cc

ls -lrt

Je kunt een kleiner getal invoeren (i.p.v. 12345) in het programma hierboven als je wilt narekenen of het antwoord klopt. (Opnieuw compileren en runnen ...) Maak ook eens expres een fout in je programma mijnsom.cc en kijk wat de compiler daarvan vindt.

tip: je kunt commando's in de terminal opnieuw oproepen met de pijltjes-toetsen, dat scheelt typwerk.

Faculteit!

Mijn computer geeft "10! = 3628800" maar ook "50! = 0" Waarom??!!

tip: Google geeft bij de zoekopdracht "50!" de waarde 3.0414093e+64 (en ook de officiele website van 50 Cent). WolframAlpha weet het precies. Waarom komt er bij ons dan nul uit? Om een verklaring te vinden kun je naar de grootst beschikbare integer INT_MAX vragen. Dat wil zeggen, je kunt een klein programmaatje schrijven dat INT_MAX opvraagt. Je hebt dan wel een extra declaratie nodig.

#include <climits>

#include <iostream>
#include <climits>
using namespace std;

int main ( ) {
   cout << "INT_MAX is " << INT_MAX << endl;
} // main

Maximum

#include <iostream>
using namespace std;

int Max (int* lijst, int van, int tot) {
   if (van==tot)
      return lijst[van];
   else {
      int linksMax, rechtsMax, half;
      half = (van+tot)/2 ;
      linksMax = Max(lijst, van, half);
      rechtsMax = Max(lijst, half+1, tot);
      if (linksMax>rechtsMax)
         return (linksMax);
      else
         return (rechtsMax);
   }
} // Max

int main ( ) {
   // de 'invoer' waarvan we het maximum gaan bepalen:
   int myarray[] = { 76, 128, 45, 2, 203, 55, 66, 1, 222 };
   int lengte = sizeof(myarray) / sizeof(int) ;
   // indices lopen van 0 tot en met lengte-1 (!!)

   cout << "Het maximum van de getallen ";
   for (int i=0; i<lengte; i++) cout << myarray[i] << ", " ;
   cout << "is: " << Max(myarray, 0, lengte-1)  << endl;
   return 0;
} // main

Opdracht. Probeer de onderdelen van het programma te herkennen. Maak nu zelf een programma om op dezelfde manier de getallen uit de lijst "myarray" bij elkaar op te tellen, dus door steeds de twee helften apart te nemen. Test je programma.

int Som (int* lijst, int van, int tot) {
   if (van==tot)
      return lijst[van];
   else {
      int linksSom, rechtsSom, half;
      half = (van+tot)/2 ;
      linksSom = Som(lijst, van, half);
      rechtsSom = Som(lijst, half+1, tot);
      return (linksSom+rechtsSom);
   }
} // Som

We gaan nu een eenvoudig spelletje recursief oplossen. Vergelijk het spel Chomp uit het proefcollege.

Nim

Bij dit soort strategie-spellen geldt de regel dat elke configuratie winnend of verliezend is (voor de speler die aan de beurt is). Een configuratie is winnend als je een zet kunt doen die een verliezende configuratie (voor de tegenstander) overhoudt. Een configuratie is verliezend als zij nul lucifers bevat, of als alle mogelijke zetten juist tot een winnende configuratie leiden. Recursie!

Een bekende Nim-variant begint met een aantal hoopjes lucifers. Elke speler pakt een willekeurig aantal lucifers uit één hoopje. Het spel is (al sinds 1901) volledig geanalyseerd, en het geheim van de winnende zet is gebaseerd op kennis van de binaire getallen.

Hier spelen we een simpeler versie van Nim. Er is slechts één hoopje lucifers, en in elke beurt mag je één of twee lucifers pakken.

Een cruciale functie van het programma bepaalt recursief wat de goede zet is. Dit is de belangrijkste functie voor Nim, en deze is hieronder te vinden. Een eenvoudig programma om deze versie van Nim en de versie die hierna komt tegen de computer (in dit geval een (domme) tegenstander, want de computer doet steeds een random zet) te spelen is hier beschikbaar: nim.cc. Onderstaande functie komt uit dat programma.

int min(int x, int y) {
// berekent het minimum van x en y
   if (x < y)
      return x;
   else
      return y;
} // min


int winnend (int lucifers){
// geeft de winnende zet terug, dat wil zeggen het
// aantal lucifers (1 of 2) dat je kan pakken om te winnen.
// als de stand niet winnend is wordt de waarde 0 geretourneerd.
// lucifers is het aantal lucifers dat op dit moment op tafel ligt

   int i;
   int maximaal;
   if (lucifers == 0)
   // verloren: tegenstander heeft net de laatste gepakt. 
      return 0;
   else {
   // alle mogelijke zetten aflopen;
      maximaal = min(2,lucifers);
      // maximaal 2 wegnemen, en niet meer dan wat er ligt

      for (i = 1; i<=maximaal; i++){
      // i lucifers weghalen
         if (winnend(lucifers - i) == 0){
         // niet winnend voor de tegenstander is winnend voor jou!
            return i;
         }
      }
      return 0;	
      // helaas geen winnende zet gevonden
   } //else

} // winnend

Opdracht. Welke beginstanden zijn winnend? Je kunt eenvoudig een programma schrijven dat de winnende aantallen lucifers afdrukt. (Gewoon in het hoofdprogramma (main) voor bijvoorbeeld de waarden 1 t/m 35 de functie winnend aanroepen.) Kun je hieruit zien wat je moet doen om te winnen met Nim?

winnend bij NIM: 1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19,
20, 22, 23, 25, 26, 28, 29, 31, 32, 34,

Fibonacci Nim

1. De eerste speler pakt een willekeurig aantal, maar niet alle lucifers (natuurlijk).
2. In elke volgende beurt mag je maximaal twee keer zoveel lucifers pakken als in de vorige beurt weggenomen zijn.

Opdracht. De functie die de winnende zet berekent lijkt sterk op die van de eerste versie van Nim. Je hebt nu echter ook in elke beurt nodig hoeveel er maximaal mogen worden weggenomen; dat hangt af van het spelverloop. De functie heeft dan ook twee parameters. Maak de functie hieronder af en test voor welke waarden deze Nim winnend is.

int winnend (int lucifers, int maxwegnemen){
// geeft de winnende zet terug, dat wil zeggen het
// aantal lucifers (maximaal maxwegnemen) dat je kan pakken om te winnen.
// als de stand niet winnend is wordt de waarde 0 geretourneerd.
// lucifers is het aantal lucifers dat op dit moment op tafel ligt

   int i;
   int maximaal;
   if (lucifers == 0)
   // verloren: tegenstander heeft net de laatste gepakt. 
      return 0;
   else {
   // alle mogelijke zetten aflopen;
      maximaal =  XXXXX ;
      // maximaal ... wegnemen, en niet meer dan wat er ligt

      for (i = 1; i<=maximaal; i++){
      // i lucifers weghalen
         if (winnend(lucifers - i, XXXXX ) == 0){
         // niet winnend voor de tegenstander is winnend voor jou!
            return i;
         }
      }
      return 0;	
      // helaas geen winnende zet gevonden
   } //else

} // winnend

Ook Fibonacci Nim is geanalyseerd, de winnende en verliezende waardes zijn bekend, maar de strategie is lastig uit te leggen.
Referentie. Michael J. Whinihan, Fibonacci Nim, The Fibonacci Quarterly, Vol. 1, 9-11, 1963.

Chomp

Opdracht. Vergelijk voor een aantal repen de tijd die het duurt om de zet te bepalen met de twee verschillende methodes. Als het lang duurt kun je het programma onderbreken met Ctrl-C.

Het spel kan met dit programma ook gespeeld worden, tegen -wederom- een domme tegenstander. De uitvoer van dit programma naar het beeldscherm is, net al bij nim.cc het geval was, zeer simpel gehouden, aangezien het in dit geval gaat om de werking, te weten het berekenen van een winnende hap.

Slot