Печать
Категория: Recur
Просмотров: 117

Recur4. Описать рекурсивную функцию Fib1(N) целого типа, вычисляющую N-й элемент последовательности чисел Фибоначчи (N — целое число):
\(F_1 = F_2 = 1, \quad F_K = F_{K-2} + F_{K-1}, \quad K = 3, 4, ...\) .
С помощью этой функции найти пять чисел Фибоначчи с данными номерами, и вывести эти числа вместе с количеством рекурсивных вызовов функции Fib1, потребовавшихся для их нахождения.

Решение на Python 3:

import random

def Fib1(N):
global call_num
call_num += 1
if N == 1 or N == 2:
#print(N," : ", 1)
return 1
y = Fib1(N-2) + Fib1(N-1)
#print(N," : ", y)
return y

#for i in range(5):
N = random.randrange(1,15)
print("N = ",N)
call_num = 0
y = Fib1(N)
print("Fibonacci Number: ", y)
print("Calls: ", call_num)