Pythonist

Описание задачи

Программа принимает на вход число членов последовательности Фибоначчи и при помощи рекурсии вычисляет все числа, входящие в эту последовательность.

Решение задачи

1. Принимаем на вход число членов последовательности и записываем его в отдельную переменную.
2. Это число передается в качестве аргумента в рекурсивную функцию, которая будет вычислять n-й член последовательности.
3. В качестве базового условия принимаем то обстоятельство, что число членов последовательности Фибоначчи не может быть меньше единицы либо равно ей. При наступление этого условия рекурсия останавливается.
4. В противном случае функция вызывается вновь следующим образом: в качестве аргумента нашей рекурсивной функции передается введенное число, уменьшенное на единицу, и к этому прибавляется эта же функция с аргументом, уменьшенным уже на 2.
5. Каждый вызов функции возвращает одно число, которое мы потом выводим на экран.

Исходный код

Ниже дан исходный код, который осуществляет вывод всех членов последовательности Фибоначчи заданного размера. Результаты работы программы также даны ниже.

def fibonacci(n):
    if (n <= 1):
        return n
    else:
        return (fibonacci(n-1) + fibonacci(n-2))
n = int(input("Введите число членов последовательности:"))
print("Последовательность Фибоначчи:")
for i in range(n):
    print(fibonacci(i))

Объяснение работы программы

1. Пользователь вводит число и оно записывается в переменную n.
2. Передаем число n в качестве аргумента в рекурсивную функцию, которая вычисляет n-ый член последовательности.
3. Так как первый член последовательности Фибоначчи по определению не может быть меньше 1, в качестве базового условия принимаем n <= 1. Когда оно выполняется, рекурсия прерывается.
4. В противном случае функция вызывается вновь следующим образом: fibonacci(n-1) + fibonacci(n-2).
5. Результаты выводятся на экран при помощи цикла for.

Результаты работы программы

Пример 1:
Введите число членов последовательности:5
Последовательность Фибоначчи:
0 1 1 2 3
 
Пример 2:
Введите число членов последовательности:7
Последовательность Фибоначчи:
0 1 1 2 3 5 8

Примечания переводчика

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