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)