C++
Rekurencja w C ++

Korzystanie z rekurencji ogona i rekurencji w stylu Fibonnaci do rozwiązania sekwencji Fibonnaci

Najprostszym i najbardziej oczywistym sposobem użycia rekurencji w celu uzyskania N-tego terminu sekwencji Fibonnaci jest:

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

Jednak ten algorytm nie skaluje się dla wyższych terminów: dla coraz większego n liczba wywołań funkcji, które należy wykonać, rośnie wykładniczo. Można to zastąpić prostą rekurencją ogona.

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

Każde wywołanie funkcji natychmiast oblicza następny termin w sekwencji Fibonnaci, więc liczba wywołań funkcji skaluje się liniowo z n .

Rekurencja z zapamiętywaniem

Funkcje rekurencyjne mogą być dość drogie. Jeśli są to funkcje czyste (funkcje, które zawsze zwracają tę samą wartość, gdy są wywoływane z tymi samymi argumentami, i które nie zależą ani nie modyfikują stanu zewnętrznego), można je znacznie przyspieszyć kosztem pamięci, przechowując wartości już obliczone.

Oto implementacja sekwencji Fibonacciego z zapamiętywaniem:

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

Zauważ, że pomimo użycia prostej formuły rekurencyjnej, przy pierwszym wywołaniu ta funkcja to $ O (n) $. Przy kolejnych połączeniach o tej samej wartości jest to oczywiście $ O (1) $.

Należy jednak pamiętać, że ta implementacja nie jest wymagana ponownie. Ponadto nie pozwala pozbyć się przechowywanych wartości. Alternatywną implementacją byłoby umożliwienie przekazania mapy jako dodatkowego argumentu:

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

W tej wersji osoba dzwoniąca jest zobowiązana do utrzymania mapy z zachowanymi wartościami. Ma to tę zaletę, że funkcja jest teraz ponownie wysyłana, a osoba dzwoniąca może usunąć niepotrzebne wartości, oszczędzając pamięć. Ma tę wadę, że przerywa enkapsulację; osoba dzwoniąca może zmienić wynik, wypełniając mapę niepoprawnymi wartościami.