Как известно, что бы понять рекурсию, надо сначала понять рекурсию. Абсолютно идиотская система, но в егэ по информатике задание на рекурсию имеет три разновидности. По названию выглядят они одинаково уродски, поэтому начнем с “Рекурсивные функции с возвращаемыми значениями”. Выглядит это примерно так:

Алгоритм вычисления значения функции F(n), где n  — целое неотрицательное число, задан следующими соотношениями:

F(0) = 0;

F(n) = F(n / 2), если n > 0 и при этом чётно;

F(n) = 1 + F(n − 1), если n нечётно.

Сколько существует таких чисел n, что 1 ≤ n ≤ 1000 и F(n)  =  3?

Как это ни печально, но придется гуглить: синтаксис функции с возвращаемым значением в питоне. Выглядит нестрашно: def, название, принимаемые значения. И ожидаемо – return где-то в конце. Так, у нас будет 3 return: для 0, для четного n и для нечетного n. В общем, нефиг тут думать, кодить надо. Для начала как-нибудь так

def f(n):
    if n == 0:
        return 0
    if (n>0) and (n%2 == 0):
        return f(n/2)
    if (n%2 != 0):
        return 1 + f(n-1)

Теперь придется вкурить, что делать с этой функцией: “Сколько существует таких чисел n, что 1 ≤ n ≤ 1000 и F(n)  =  3?”

Напрашивается цикл for от 1 до 1000, в цикле вызывать эту несчастную f, и если она вернет значение “3”, наращивать счетчик. Поехали.

count = 0
for i in range (1, 1000):
    if f(i) == 3:
        count = count + 1
print(count)

Заодно выяснилось, что в питоне после функции надо отступить две пустые строчки, IDE подсвечивала PEP 8: E305. Это вроде как необязательно, но если питон такой нервный, ок, добавлю две пустые строчки, мне не жалко. И опять почти не пришлось ничего отлаживать, что же такое-то.

Так, день прошел не зря, потратился всего час; завтра посмотрим, насколько этот час был продуктивен, тем более, что завтра будет День третий. Скорость решает.