Задача 16 - рекурсивная функция

Хотите готовиться со мной к ЕГЭ?
Пишите: ydkras@mail.ru
Немного обо мне.

 

Задача 16 ЕГЭ по информатике посвящена рекурсивным функциям. 

Рекурсивные функции - такие функции, которые обращаются к самим себе.

Рассмотрим задачу 16 из демонстрационного варианта ЕГЭ 2022 г. с сайта ФИПИ:

Алгоритм вычисления значения функции 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(1), F(2) и т.д. - до F(26) включительно. Но составлять таблицу из 26 строк вручную несколько трудоемко, да и вероятность ошибиться ненулевая. Гораздо проще составить эту таблицу в excel.  

Но, на мой взгляд, ещё проще решать данную задачу программно.

Сначала напишем рекурсивную функцию на Питоне:

def F(n):
    if n==1: return 1
    if n%2 == 0: return n+F(n-1)
    return 2*F(n-2)

Просто, не так ли? Мы практически переписали определение функции строчка в строчку. 

А почему в последней строке нет условия? Всё очень просто: оператор return прекращает вычисление функции, поэтому если, например, n равно 1, то операторы после строки, в которой проверяется соответствующее условие,  выполняться не будут. Поэтому если выполнение дошло до последней строки функции, то случаи n, равного единице и четного n исключены.

Теперь мы можем узнать ответ данной задачи, написав дополнительно лишь строку 

print(F(26)) 

(Ответ равен 4122.)

На сайте К.Полякова задачи на рекурсивные функции более сложны, но и их решить программным путем обычно очень просто. 

Рассмотрим, например, задачу из варианта 8:

(№ 3820) Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:
F(n) = 1, при n < 2,
F(n) = F(n/3) - 1, когда n ≥ 2 и делится на 3,
F(n) = F(n - 1) + 7, когда n ≥ 2 и не делится на 3.
Назовите минимальное значение n, для которого F(n) равно 111.

Приведем полную программу для решения этой задачи:

def F(n):
    if n<2: return 1
    if n%3 == 0: return F(n//3)-1
    return F(n-1)+7

n=1
while True:
    if F(n)==111:
        print(n)
        break
    n += 1

 

Легко видеть, что мы организуем бесконечный цикл и последовательно вычисляем F(1), F(2) и т.д. Как только F(n) будет равно 111, это значение печатается и цикл прерывается.

В данном случае ответ равен 32804. Перебрать вручную такое количество значений n нереально, поэтому в данном случае программный способ - единственно разумный метод решения.

К сожалению, не всегда эти задачи решаются столь просто. Ниже будут рассмотрены некоторые "подводные камни", которые встречатся в задачах на рекурсию. 

Недопустимо медленная рекурсивная функция

Рассмотрим такую задачу:

Пусть  имеется следующая функция F(n):

F(n)=1 при n<3;
F(n)=F(n-1)+F(n-2) при n>=3.

Чему равно F(45)?

Казалось бы, всё просто. Пишем программу из четырех строчек:

def F(n):
    if n<3: return 1
    return F(n-1)+F(n-2)
print (F(45))

Запускаем программу и... не можем дождаться, когда она выполнится и отпечатает результат.

В чем тут дело? А в том, что для того, чтобы вычислить, например, F(10), нам требуется вычислить F(9) и F(8). Для вычисления F(9) и F(8) будут вычислены F(8), F(7), F(7) и F(6). Как можно видеть, значения функции для одного и того же параметра многократно перевычисляются, а увеличение n на 1 приводит к увеличению объёма (и времени) вычислений примерно в два раза. 

Вот таблица, показывающая время вычисления функции F(n) для различных n.

n	F(n)	Время, с
33	3524578	1.40
34	5702887	2.31
35	9227465	4.21
36	14930352	6.91
37	24157817	11.24
38	39088169	18.93
39	63245986	31.45
40	102334155	57.24
41	165580141	104.53

Как говорится, тенденция налицо, и понятно, что дождаться, когда такая функция вычислит F(45), непросто. 

Какой же выход из данной ситуации?

Во-первых, можно перейти на какой-либо более эффективный язык (паскаль или C++). Но даже эти языки не спасут, если потребуется вычислить, скажем, F(100).

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

def F(n):
    if n<3:
        return 1
    f1=1
    f2=1
    f3=f1+f2
    i=3  
    while i<n:
        f1=f2
        f2=f3
        f3=f1+f2
        i += 1
    return f3  
print(F(45)) 

Эта программа выполняется мгновенно.

Но в случае более сложной функции написать её нерекурсивный эквивалент может оказаться непростым делом. Гораздо проще сделать так, чтобы ранее вычисленные значения нашей функции повторно не вычислялись. Для этого воспользуемся структурой данных, которая называется "ассоциативный массив" или "словарь". В этой структуре хранятся пары "ключ"-"значение". В нашем случае ключом будет входной параметр n, а значением - значение функции F(n).

Вот программа, использующая словарь:

def F(n):
    if not n in f:
        if n < 3:
            f[n] = 1
        else:
            f[n] = F(n-1)+F(n-2)
    return f[n]
    
f={}
print(F(45))

Функция F(n) проверяет, есть ли значение n в словаре f. Если нет, то это значение вычисляется и заносится в словарь (в строках вида f[n]=...). Если же такое значение уже есть, то ничего вычислять не надо. В последней строке функция возвращает значение f[n] из словаря f.

Перед вызовом функции в основной программе создается пустой словарь f (в строке f={}). 

Если воспользоваться условным выражением if-else, то вышеприведенную программу можно сильно сократить:

def F(n):
    if not n in f:
        f[n] = 1 if n < 3 else F(n-1)+F(n-2)
    return f[n]
    
f={}
print(F(45))

Когда рекурсия не завершается

(Продолжение следует немного позже.)

 

(c) Ю.Д.Красильников, 2021-2022 г.