Реализация формулы через рекурсию

Мы можем сделать реализацию в лоб на основе рекурсии. Формула нам говорит, что любое входящее число 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. Чем сильней разрастается граф, тем нам понятней, что его можно очень сильно оптимизировать.

Если вы нашли ошибку, пожалуйста выделите её и нажмите Ctrl+Enter.


Leave a Reply

Your email address will not be published. Required fields are marked *