Мы можем сделать реализацию в лоб на основе рекурсии. Формула нам говорит, что любое входящее число N – это сумма чисел N-1 и N-2. И есть базовые случаи при N равным 0 и 1. Мы упростим базовый случай сказав, что при любом N, меньше 3, результат будет равен 1.
В результате мы получим такую реализацию.
Фрагмент 2.49
static int Fibonacci(int n)
{
if (n < 3) return 1;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}Она дает правильный ответ, но не за адекватное время. К сожалению, рост количества вызовов функций – экспоненциальный. Чтобы понять это, можно посмотреть на граф вызовов. Функция работает таким образом, что на вызов от N происходит множество подобных вызовов внутри себя (рекурсивно), но с другими N. В процессе рекурсии мы очень часто повторяемся и множество раз рассчитываем N повторно.
На этом графе видно, что ветви рекурсии содержат идентичные вызовы, это и не позволяет получить приемлемое время выполнения при большом N. Чем сильней разрастается граф, тем нам понятней, что его можно очень сильно оптимизировать.
