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

Последовательность Фибоначчи — это ряд целых чисел 0, 1, 1, 2, 3, 5, 8, …

Первые два члена равны 0 и 1. Любой следующий получается сложением двух предыдущих, то есть n-й член равен сумме (n-1)-го и (n-2)-го.

Что нужно знать

Пример

# Python: вывод последовательности Фибоначчи

def recur_fibo(n):
   if n <= 1:
       return n
   else:
       return(recur_fibo(n-1) + recur_fibo(n-2))

nterms = 10

# проверяем, что количество членов корректно
if nterms <= 0:
   print("Plese enter a positive integer")
else:
   print("Fibonacci sequence:")
   for i in range(nterms):
       print(recur_fibo(i))

Вывод

Fibonacci sequence:
0
1
1
2
3
5
8
13
21
34

Примечание

Чтобы проверить программу на другом количестве членов, поменяйте значение nterms.

В программе количество членов хранится в nterms. Рекурсивная функция recur_fibo() вычисляет n-й член последовательности, а цикл for перебирает индексы и печатает каждый член по очереди.

Как это работает

Функция recur_fibo(n) опирается на определение: F(n) = F(n-1) + F(n-2), с базовыми случаями F(0) = 0 и F(1) = 1. При n <= 1 возвращается само n, иначе функция складывает два своих рекурсивных вызова. Такой вариант нагляден, но при больших n неэффективен из-за повторных пересчётов.