C++
Recursie in C ++

Tail recursion en Fibonnaci-style recursion gebruiken om de Fibonnaci-reeks op te lossen

De eenvoudige en meest voor de hand liggende manier om recursie te gebruiken om de Nde term van de Fibonnaci-reeks te krijgen, is deze

int get_term_fib(int n)
{
  if (n == 0)
    return 0;
  if (n == 1)
    return 1;
  return get_term_fib(n - 1) + get_term_fib(n - 2);
}

Dit algoritme schaalt echter niet voor hogere termen: voor grotere en grotere n groeit het aantal functieaanroepen dat u moet doen exponentieel. Dit kan worden vervangen door een eenvoudige staartrecursie.

int get_term_fib(int n, int prev = 0, int curr = 1)
{
  if (n == 0)
    return prev;
  if (n == 1)
    return curr;
  return get_term_fib(n - 1, curr, prev + curr);
}

Elke aanroep van de functie berekent nu onmiddellijk de volgende term in de Fibonnaci-reeks, dus het aantal functieaanroepen wordt lineair geschaald met n .

Herhaling met memoisatie

Recursieve functies kunnen behoorlijk duur worden. Als het pure functies zijn (functies die altijd dezelfde waarde retourneren wanneer ze met dezelfde argumenten worden aangeroepen, en die niet afhankelijk zijn van externe status of deze niet wijzigen), kunnen ze aanzienlijk sneller worden gemaakt ten koste van geheugen door de reeds berekende waarden op te slaan.

Het volgende is een implementatie van de Fibonacci-reeks met memoisatie:

#include <map>

int fibonacci(int n)
{
  static std::map<int, int> values;
  if (n==0 || n==1)
    return n;
  std::map<int,int>::iterator iter = values.find(n);
  if (iter == values.end())
  {
    return values[n] = fibonacci(n-1) + fibonacci(n-2);
  }
  else
  {
    return iter->second;
  }
}

Merk op dat, ondanks het gebruik van de eenvoudige recursieformule, deze functie bij de eerste aanroep $ O (n) $ is. Bij volgende oproepen met dezelfde waarde is dit natuurlijk $ O (1) $.

Merk echter op dat deze implementatie niet terugkomt. Het staat ook niet toe om opgeslagen waarden kwijt te raken. Een alternatieve implementatie zou zijn om de kaart als extra argument door te laten:

#include <map>

int fibonacci(int n, std::map<int, int> values)
{
  if (n==0 || n==1)
    return n;
  std::map<int,int>::iterator iter = values.find(n);
  if (iter == values.end())
  {
    return values[n] = fibonacci(n-1) + fibonacci(n-2);
  }
  else
  {
    return iter->second;
  }
}

Voor deze versie moet de beller de kaart onderhouden met de opgeslagen waarden. Dit heeft het voordeel dat de functie nu opnieuw aanwezig is en dat de beller waarden die niet langer nodig zijn kan verwijderen, waardoor geheugen wordt bespaard. Het heeft het nadeel dat het inkapseling breekt; de beller kan de uitvoer wijzigen door de kaart te vullen met onjuiste waarden.