Задача

Алгоритм вычисления значения функции 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.

Решение (Программа, Паскаль)

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

Подпрограмма - поименованная или иным образом идентифицированная часть компьютерной программы, содержащая описание определённого набора действий. Подпрограмма может быть многократно вызвана из разных частей программы.

В Паскале подпрограмма — и функция и процедура.

Между функциями и процедурами есть существенное отличие. Значение, полученное в результате выполнения кода функции, жестко соотносится с ее именем путем присвоения этому имени конкретного значения. Тип, который может принять вычисляемое значение, указывается в заголовке функции (тип результата). И в теле основной программы функция вызывается только в том случае, если ее имя фигурирует в каком-либо выражении. В то время как процедура вызывается отдельно.

Функция описывается в разделе описания переменных и имеет следующий синтаксис:

Program Name;
  var …;{область объявления глобальных переменных}
  function название (параметры); {начало процедуры}
      begin 
        …  {тело процедуры}
      end;{конец процедуры}
begin
  … {основная программа}
end.

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

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

Program N_16;
  var a:integer;
  function func (x:integer):integer;
    begin
        if n=1 then
          func:=1
        else
          if n mod 2 = 0 then
            func:=n + func(n-1)
          else
            func:=2*func(n-2);
      end;
begin
  writeln('Введите число');
  read(a);
  write('F(',a,')=',func(a))
end.

Решение (Программа, Питон)

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

В нашем в функции будет использоваться одна целочисленная переменная - 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)
a=int(input())
print('F(',a,')=',func(a))