Рекурсивная функция на Python

Как перевести определение функции на Python?

Функцию записывают прямо по определению: база — проверка и return с готовым числом, рекуррентное соотношение — return с вызовом той же функции. Вот функция задачи темы. Нажми «Запуск» и пройди программу по шагам:

def F(n):    if n == 1:        return 1    return n * F(n - 1)  print(F(5))

Разберём строки по порядку:

• def F(n): создаёт функцию F. n — её параметр: при вызове F(5) в n попадает 5;
• if n == 1: — проверка. Двойной знак == сравнивает, а одинарный = присваивает;
• return 1 завершает вызов и отдаёт 1 туда, откуда функцию вызвали. Строки ниже в этом вызове уже не выполняются;
• return n * F(n - 1) вызывает F(n − 1), ждёт ответа, умножает его на n и отдаёт результат.

В пошаговом запуске видно то же, что мы делали вручную: вызовы F(5), F(4), F(3), F(2) ждут, у каждого своё n, а после базы возвращаются 1, 2, 6, 24, 120.

Как записать формулу с ветвями?

Каждая ветвь определения — своя проверка: if, затем elif («иначе, если»), а для последней — else («иначе»). Функция с ветвями из прошлой подтемы:

def F(n):    if n <= 2:        return n    elif n % 2 == 0:        return F(n - 1) + n    else:        return 2 * F(n - 2)  print(F(8))

Чётность проверяют остатком от деления на 2: % — остаток, и n % 2 == 0 значит «n чётно». Ветвь Python выбирает в каждом вызове по его собственному n — как мы делали вручную. Программа печатает 16.

Всегда ли программа по определению досчитает до конца?

Только если от нужного аргумента все вызовы доходят до базы. Например: F(1) = 1; F(n) = F(n − 2) + n при n > 1. Для F(7) аргументы 7, 5, 3, 1 — база достигнута. Для F(6) — 6, 4, 2, 0, −2, … База пропущена: вычитание 2 не меняет чётность.

Навечно программа на F(6) не зависнет: когда ждущих вызовов станет около тысячи, Python остановит её ошибкой RecursionError — превышен предел глубины рекурсии.

Поэтому перед программой проверь по условию:

• какие аргументы допустимы: «натуральное» — 1, 2, 3, …, «целое неотрицательное» — 0, 1, 2, …;
• куда ведут переходы — вниз или вверх и через сколько чисел;
• попадает ли каждая нужная цепочка в базу.

В задачах экзамена база подобрана так, что нужные вызовы до неё доходят. Проверка спасает от ошибки при переписывании: если в условии база «n ≤ 1», а в программе if n == 1, чётная цепочка пролетит мимо.

Как решить задачу темы программой?

Функция уже есть — осталось напечатать выражение из условия. Но прямой запуск остановится ошибкой:

print((F(2026) + 3 * F(2025)) // F(2024))

F(2026) ждёт F(2025), тот — F(2024), и так до F(1): больше двух тысяч ждущих вызовов. А Python по умолчанию разрешает около тысячи. Предел поднимают в начале программы:

import sys sys.setrecursionlimit(5000)  def F(n):    if n == 1:        return 1    return n * F(n - 1)  print((F(2026) + 3 * F(2025)) // F(2024))

import sys подключает модуль с настройками Python, а sys.setrecursionlimit(5000) разрешает до 5000 ждущих вызовов — с запасом для 2026. Ответ задачи темы — 4 108 725.

Деление записано через //: выражение делится нацело (почему — увидим в подтеме 4), а // делит целые числа точно. Обычное / напечатало бы дробное 4108725.0.

• def F(n):функция с параметром n
• if n == 1: return 1база — ответ без нового вызова
• return n * F(n - 1)рекуррентное соотношение — вызов себя
• if / elif / elseветви, Python выбирает их в каждом вызове
• До базыкаждая нужная цепочка аргументов попадает в базу
• sys.setrecursionlimitбольше ждущих вызовов — для аргументов в тысячи
• //точное деление нацело