C++
Рекурсия в C ++

Используя рекурсию хвоста и рекурсию в стиле Фибонаци, чтобы решить последовательность Фибонаци

Простым и очевидным способом использования рекурсии для получения N-го члена последовательности Фибонаци является

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

Однако этот алгоритм не масштабируется для более высоких терминов: для большего и большего числа n количество вызовов функций, которые вам нужно сделать, растет экспоненциально. Это можно заменить простой хвостовой рекурсией.

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

Каждый вызов функции теперь сразу вычисляет следующий член в последовательности Fibonnaci, поэтому число вызовов функций линейно масштабируется с n .

Рекурсия с воспоминаниями

Рекурсивные функции могут стать довольно дорогими. Если они являются чистыми функциями (функции, которые всегда возвращают одно и то же значение при вызове с теми же аргументами и не зависят ни от внешнего состояния, ни изменяют его), они могут быть сделаны значительно быстрее за счет памяти, сохраняя уже рассчитанные значения.

Ниже приведена реализация последовательности Фибоначчи с 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;
  }
}

Обратите внимание, что, несмотря на использование простой формулы рекурсии, при первом вызове эта функция равна $ O (n) $. При последующих вызовах с одинаковым значением, конечно, $ O (1) $.

Обратите внимание, однако, что эта реализация не является повторной. Кроме того, он не позволяет избавиться от сохраненных значений. Альтернативной реализацией было бы разрешить передачу карты в качестве дополнительного аргумента:

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

Для этой версии вызывающий абонент должен поддерживать карту с сохраненными значениями. Это имеет то преимущество, что функция теперь является реентерабельной, и что вызывающий может удалить значения, которые больше не нужны, сохраняя память. Недостаток заключается в том, что он разрушает инкапсуляцию; вызывающий может изменить вывод, заполнив карту неверными значениями.