Rekursion

Rekursion är ett begrepp som brukar förknippas med funktionell programmering. Trots att C++ är ett imperativt språk kan man även här använda rekursion för att lösa olika problem. Rekursion innebär som bekant att funktioner kan anropa sig själv. Rekursion är inte alltid det mest optimala förfaringsättet i C++, men i vissa fall är det väldigt praktiskt, och kan t.o.m. vara effektivare on iterativ kod. T.ex. vid hantering av träd av olika typ är rekursion en ovärderlig resurs. Ett standardexempel på rekursion torde vara hur n! (n-fakultet) räknas ut rekursivt:

#include <iostream>

unsigned int Fakultet (unsigned int N) {
  if ( N == 0 ) {
    // basfallet nått
    return 1;
  }

  return N * Fakultet ( N - 1 );
}

int main () {
  unsigned int Tal;
  cout << "Ge in ett tal: ";
  cin >> Tal;

  // beräkna fakulteten och skriv ut svaret
  cout << Tal << "! = " << Fakultet ( Tal ) << endl;
}

Man bör dock se upp för oändlig eller alltför djup rekursion, eftersom det leder till problem med programmets stack, vilket i sin tur leder till problem i exekveringen. Ett annat exempel på rekursiv programmering är beräkning av Fibonacci-tal. Fibonacci-talet fib(n) definieras som fib(n-1) + fib(n-2), där fib(0) = 0 och fib(1) = 1. Vi kan nu använda denna definition för att skapa en enkel implementation.

#include <iostream>

unsigned int fib (unsigned int N) {
  if ( N == 0 ) {
    // basfall 1 nått
    return 0;
  }

  if ( N == 1 ) {
    // basfall 2 nått
    return 1; 
  }

  // almänt fall, använd rekursion
  return fib ( N - 1 ) + fib ( N - 2 );
}

int main () {
  unsigned int Tal;
  cout << "Ge in ett tal: ";
  cin >> Tal;

  // beräkna fakulteten och skriv ut svaret
  cout << Tal << "! = " << fib ( Tal ) << endl;
}