Рекурсивное нахождение чисел Фибоначчи на C++

Задачи по вычислению числа из ряда чисел Фибоначчи очень часто встречаются при изучении программирования на языке C++. В этой статье я расскажу об одном алгоритме, который может решить эту задачу. Если Вас интересуют другие задачи, то загляните в раздел с решениями задач по программированию.

Числа Фибоначчи — это числовая последовательность, в которой каждый следующий член равен сумме двух предыдущих. Первые два члена равны единице. Нулевой член  равен нулю, но чаще всего его не рассматривают как элемент последовательности, и тогда ряд чисел Фибоначчи имеет вид:  1, 1, 2, 3, 5, 8, 13, 21, … — такой вид он имеет и в отрицательную сторону с отрицательным знаком.

Пример последовательности от -5-го до 5-го члена: -5, -3, -2, -1, -1, 0, 1, 1, 2, 3, 5

В задачах обычно требуется найти n-ый член последовательности.

Рекурсивное решение на C++

Рекурсия

Рекурсия

Очень часто рекурсию в программировании показывают на примере вычисления чисел Фибоначчи рекурсивным алгоритмом. Такой алгоритм довольно прост, но время выполнение растет по экспаненте при увеличении n. Поэтому алгоритм работает медленно при больших n, а также может произойти переполнение стека(Stack Overflow).

Для решения создадим функцию f(n), в качестве аргумента она будет получать число n. Эта функция будет возвращать число, которое будет равно f(n-1) + f(n-2). То есть она вызывает себя 2 раза из самой себя.

Теперь добавим возвращемое значение для f(0), f(1), f(2), чтобы при вызове функции с такими агрументами функция прекращала вызывать себя и выдавала значение. Для f(0) возвращаемое значение будет 0. Для f(1) и f(2) 1.

Обратите внимание, функция возвращает значение с типом unsigned long long int. Это позволит ей выводить огромные числа (от 0 до 18 446 744 073 709 551 615), а значит она сможет работать с большими n.

Таким образом данная функция вычисляет n-ое число из ряда чисел Фиббоначи. Функция работает только с n >= 0.

В ходе работы функция вызывает сама себя, раскладывается, пока не вызовет f(1) или f(2), которые тут же возвратят 1 и не будут делать больше ничего. После этого функция обратно «складывается».

Для примера напишем программу с вызовом функции f() с аргументом 5 и выведем результат.

Результат выполнения программы

Вычисленное число Фибоначчи

Вычисленное число Фибоначчи

Под капотом всё происходило примерно так: функция f(5) вызвала 2 функции f(4) и f(3); функция f(4) вызвала функции f(3) и f(2), а функция f(3) вызвала функции f(2) и f(1) и так далее… Но, для наглядности посмотрите на рисунок.

Вызовы функции f()

Вызовы функции f()

Стрелочка, выходящая из прямоугольника с функцией, показывает возвращаемое значение.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *