Задача

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n + F(n − 1), если n – чётно,
F(n) = 2 × F(n − 2), если n > 1 и при этом n – нечётно.
Чему равно значение функции F(26)?

Решение (аналитическое)

Обратите внимание на то, что значение F(n) задано рекурсивной функцией.

Рекурсивная функция - это числовая функция f(n) числового аргумента, которая в своей записи содержит себя же.

 Т.к. 26 - четное, то:

25 - не четное:

23 - не четное:

Обращаем внимание на то, что в дальнейшем все n будет не четными.

Задача сводится к тому, чтобы выяснить сколько таких нечетных значений n будет.

Чисел - 12 (25 - 23 - 21 - 19 - 17 - 15 - 13 - 11 - 9 - 7 - 5 - 3). При n=1 значение функции нам известно F(n) = 1.

12 раз 2 умножается сама на себя - это степень числа 2.

Ответ: 4122.

Решение (программа)

Рекурсия на Phyton записывается через подпрограмму.

В нашем случае в функции будет использоваться одна целочисленная переменная - n. А сама функция будет иметь имя func. Тело функции будет состоять из условного оператора, который по n будет определять как считать func.

Таким образом алгоритм будет иметь следующий вид:

def func (n):
    if n==1:
    	return 1
    elif n%2 == 0:
    	return n + func(n-1)
    else:
    	return 2*func(n-2)
print(func(26))