C++
Récursivité en C ++

Utilisation de la récursion de la queue et de la récursion de style Fibonnaci pour résoudre la séquence Fibonnaci

La manière la plus simple et la plus évidente d’utiliser la récursivité pour obtenir le Nième terme de la séquence Fibonnaci est la suivante:

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

Cependant, cet algorithme ne s’adapte pas aux termes plus élevés: pour les n plus grands, le nombre d’appels de fonctions à effectuer augmente de manière exponentielle. Cela peut être remplacé par une simple récursion de la queue.

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

Chaque appel à la fonction calcule maintenant immédiatement le terme suivant dans la séquence Fibonnaci, de sorte que le nombre d'appels de fonction évolue linéairement avec n .

Récursivité avec mémo

Les fonctions récursives peuvent devenir assez coûteuses. Si ce sont des fonctions pures (fonctions qui renvoient toujours la même valeur lorsqu'elles sont appelées avec les mêmes arguments et qui ne dépendent ni ne modifient l'état externe), elles peuvent être considérablement accélérées au détriment de la mémoire en stockant les valeurs déjà calculées.

Ce qui suit est une implémentation de la séquence de Fibonacci avec mémo:

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

Notez que malgré l'utilisation de la formule de récurrence simple, cette fonction est $ O (n) $ au premier appel. Sur les appels suivants avec la même valeur, c'est bien sûr $ O (1) $.

Notez cependant que cette implémentation n'est pas réentrante. En outre, il ne permet pas de se débarrasser des valeurs stockées. Une autre implémentation serait de permettre à la carte d'être transmise en tant qu'argument supplémentaire:

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

Pour cette version, l'appelant doit conserver la carte avec les valeurs stockées. Cela a l'avantage que la fonction est maintenant réentrante et que l'appelant peut supprimer des valeurs inutiles, économisant ainsi de la mémoire. Il présente l'inconvénient de rompre l'encapsulation; l'appelant peut modifier la sortie en renseignant la carte avec des valeurs incorrectes.