C++
Rekursion i C ++

Använda svansrekursion och rekursion i Fibonnaci-stil för att lösa Fibonnaci-sekvensen

Det enkla och mest uppenbara sättet att använda rekursion för att få Nth-termen i Fibonnaci-sekvensen är detta

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);
}

Denna algoritm skalas inte för högre termer: för större och större n växer antalet funktionssamtal som du behöver göra exponentiellt. Detta kan ersättas med en enkel svansrekursion.

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);
}

Varje samtal till funktionen beräknar nu omedelbart nästa term i Fibonnaci-sekvensen, så antalet funktionssamtal skalar linjärt med n .

Rekursion med memoization

Rekursiva funktioner kan bli ganska dyra. Om det är rena funktioner (funktioner som alltid returnerar samma värde när de kallas med samma argument, och som varken är beroende av eller modifierar externt tillstånd), kan de göras betydligt snabbare på bekostnad av minnet genom att lagra de redan beräknade värdena.

Följande är en implementering av Fibonacci-sekvensen med memoization:

#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;
  }
}

Observera att trots att den enkla rekursionsformeln används är denna funktion $ O (n) $ vid första samtalet. På efterföljande samtal med samma värde är det naturligtvis $ O (1) $.

Observera dock att denna implementering inte är re-centrerad. Det tillåter inte heller att bli av med lagrade värden. Ett alternativt genomförande skulle vara att låta kartan skickas som ytterligare argument:

#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;
  }
}

För denna version krävs den som ringer att behålla kartan med de lagrade värdena. Detta har fördelen att funktionen nu är centrifugerad och att den som ringer kan ta bort värden som inte längre behövs, vilket sparar minne. Det har nackdelen att det bryter inkapsling; den som ringer kan ändra utgången genom att fylla kartan med felaktiga värden.