Сколько раз будет вызвана функция f def f n if n 0 return 1 return n f n 2 f 50
Ниже на пяти языках программирования записаны две рекурсивные функции (процедуры): F и G.
procedure F(n: integer); forward;
procedure G(n: integer); forward;
procedure F(n: integer);
begin
if n > 0 then
G(n — 1);
end;
procedure G(n: integer);
begin
writeln(‘*’);
if n > 1 then
F(n — 3);
end;
void F(int n);
void G(int n);
Сколько символов "звёздочка" будет напечатано на экране после выполнения вызова F(11)?
Источник: демоверсия ФИПИ по информатике и ИКТ 2016-го года.
В решении задания есть видеоразбор
Рекурсивная функция — это функция, вызывающая сама себя. Нам даны две процедуры со взаимной рекурсией, то есть процедура F вызывает процедуру G, а процедура G — процедуру F.
Как мы видим, символ "звёздочка" выводится на экран при вызове процедуры G, при этом "звёздочка" печатается в любом случае, независимо от условия.
То есть для решения задания нам достаточно определить, сколько раз будет вызвана процедура G при вызове F(11).
Вызовы процедур мы можем записать так:
На процедуре F(-1) рекурсия завершится, так как условие n>0 перестанет выполняться.
Осталось посчитать, сколько раз была вызвана процедура G:
F(11) -> G(10) -> F(7) -> G(6) -> F(3) -> G(2) -> F(-1)
Рекурсия — Python: Функции
"Чтобы понять рекурсию, нужно сначала понять рекурсию!" (расхожая шутка).
Рекурсия в программировании — это возможность дать определение функции, используя в процессе саму определяемую функцию. В математике многие функции определены именно таким образом, поэтому и большинство языков программирования берёт на вооружение этот подход. Python здесь не является исключением: обычно в определении функции вы можете использовать только определения, данные ранее, но есть одно исключение — функция в своём теле может вызывать себя. Выглядит это так:
Эта функция, вычисляет факториал числа n через умножение числа на факториал числа n — 1 .
Условие завершения рекурсии
Рассмотренный пример демонстрирует использование условия, прекращающего рекурсию. Если в этой функции убрать условие, проверяющее аргумент на неотрицательность, то первый же вызов этой функции заставит программу "зациклиться" — функция продолжит вызывать себя снова и снова.
В определениях рекурсивных функций практически всегда присутствует подобное условие. Оно позволяет вычислению пойти по одной из веток: по рекурсивной — в этой ветке произойдёт вызов себя (а то и не один!), и терминальной, которая закончит вычисление и вернёт результат.
Есть даже такое правило: какой-то из аргументов рекурсивной функции должен обязательно "убывать". Убывание может означать уменьшение счётчика, отбрасывание "головы" списка при движении к его хвосту, вызов себя для части исходной структуры при обработке древовидных структур данных. К сожалению, в общем случае понять, что программа не зациклится, можно только методом "пристального взгляда" и применением тестов. Особенно важно проверять срабатывание условия завершения рекурсии!
Переполнение стека
В большинстве программ, написанных на языках, которые поддерживают вызов функций, этот самый вызов устроен так: перед вызовом функции текущее место в программе запоминается в стеке, а когда функция возвращает результат, то соответствующий элемент стека отбрасывается.
Стек (stack) — абстрактный тип данных, похожий на стопку монет: монета, положенная последней, будет снята первой (при снятии монет порядок получается обратным порядку складывания).
В этом же стеке сохраняются значения аргументов функции, а иногда и другая служебная информация. При этом память, выделенная для стека при запуске программы, конечна и довольно ограничена. Что же произойдёт, если функция будет вызывать себя снова и снова и не возвращать результат? Эта память когда-нибудь закончится! Когда заканчивается память, выделенная для стека вызовов, случается так называемое "переполнение стека".
Из-за переполнения стека вы не сможете посчитать факториал для достаточно больших чисел с помощью рекурсивной функции. Но сможете посчитать с помощью итеративной — написанной с использованием циклов и переменных. К слову, вот так выглядит переполнение стека при подсчёте факториала:
Заметьте, сообщение говорит, что "превышена максимальная глубина рекурсии". Глубиной рекурсии называется количество последовательных вызовов "себя" без возврата значения. В Python максимальная длина искусственно ограничена, потому что проще считать количество вызовов, чем предсказывать окончание памяти.
Зачем рекурсия нужна
Вы можете подумать, почему же программисты не перестают использовать рекурсивные функции и не переходят на итеративные? Дело в том, что некоторые алгоритмы реализуются сильно проще, если использовать именно рекурсию, а не циклы. Часто такие алгоритмы работают с рекурсивными же структурами данных — деревьями, "словарями словарей словарей" и подобными. При реализации таких алгоритмов нужно помнить, что память для стека не бесконечна. Впрочем, обычно не бесконечны и сами обрабатываемые структуры данных, поэтому отказываться полностью от рекурсии не стоит!
Рекурсия прямая, косвенная, линейная, каскадная
Видов рекурсии существует несколько. Если функция вызывает себя непосредственно, то мы имеем дело с прямой рекурсией. Если же функция вызывает внутри себя другую, которая когда-то вызовет первую, то это уже косвенная рекурсия.
Если при вычислении результата функции нужно вызвать себя один раз, как в примере с factorial , то рекурсия называется линейной. Только имейте в виду, что "один раз" ничего не говорит про общее количество вызовов функции в теле! Речь идёт именно о количестве вызовов, результаты которых потребуются для одного общего вычисления.
Рассмотрим два разных примера: в одном рекурсия будет линейной, а в другом каскадной — так называют рекурсию с "несколькими вызовами себя".
Рекурсия в этой функции (которая проверяет Гипотезу Коллатца) — линейная:
Здесь в теле функции рекурсивных вызова два, но в каждом конкретном "заходе" используется только один.
А вот рекурсия в этой функции (которая вычисляет очередное Число Фибоначчи) — каскадная:
Здесь функция всегда вызывает себя два раза. Сначала будет два вызова себя, которые превратятся в четыре (два раза по два вызова), затем в восемь — количество вызовов растёт "каскадно", отсюда и название рекурсии.
Открыть доступ
Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.
ЕГЭ по информатике 2022 — Задание 16 (Рекурсия)
Шестнадцатое задание из ЕГЭ по информатике 2022 даётся на рекурсию.
Это задание нужно делать с помощью компьютера.
В программировании рекурсией называется процесс, когда функция вызывает сама себя или, когда две функции попарно вызывают друг друга.
Мы будем писать все программы на языке программирования Python.
Что такое Функция в языке программирования Python ?
Рассмотрим пример функции, которая суммирует два числа!
Здесь функция F, которая суммирует два числа.
В главной части программы запрашиваются два числа с клавиатуры: a и b! Эти два числа передаются в функцию F. В функции эти числа кладутся в локальные переменные x и y. Сумма переменных x и y записывается в переменную s. Переменная s возвращается, как результат работы функции F.
Результат работы функции будет помещён в переменную r (в строке r = F(a, b)) в основной части программы.
Таким образом, в переменной r будет сумма двух переменных a и b.
Функции позволяют сократить программный код для однотипных расчётов.
Тренировочные задачи 16 задания из ЕГЭ по информатике 2022
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n + F(n − 1), если n – чётно,
F(n) = 3 × F(n − 2), если n > 1 и при этом n – нечётно.
Чему равно значение функции F(25)?
Напишем программу для решения данной задачи. В начале опишем все правила, которые даны в условии задачи для функции. В основной части программы запустим эту функцию.
После запуска рекурсивной функции программа выведет ответ 531441.
Выражение n%2 != 0 (остаток от деления на «2» не равен нулю) обозначает нечётное число. Выражение n%2==0 обозначает чётное число.
Ответ: 531441
Продолжаем тренировку по подготовке к 16 заданию ЕГЭ по информатике 2022.
Задача (Продолжаем подготовку)
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(2) = 3
F(n) = F(n–1) * n + F(n–2) * (n – 1) , при n > 2
Чему равно значение функции F(8)? В ответе запишите только натуральное число.
Ответ получается 148329.
Ответ: 148329
Закрепляющий пример на рекурсию 16 задания из ЕГЭ по информатике 2022.
Алгоритм вычисления значения функций F(n) и G(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 0, если n 2
Чему равно значение функции F(8)? В ответе запишите только натуральное число.
Получается ответ 9.
Задача (Количество значений)
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 2*n*n*n + 1, при n > 25
F(n) = F(n+2) + 2*F(n+3), при n ≤ 25
Определите количество натуральных значений n из отрезка [1; 1000], для которых значение F(n) кратно 11.
В начале формируем функцию F. Затем перебираем числа из диапазона от 1 до 1000. Каждое число подставляем в функцию F. Если значение функции F делится на 11, то мы зачитываем такое значение i.
В ответе получается 91.
Задача (Используем глобальную переменную)
Решение:
При решении этой задачи можно применить глобальную переменную.
Здесь внутри функции заводим глобальную переменную s, которая будет подсчитывать количество напечатанных звёздочек. Теперь эту переменную видно при любом вызове функции, и при каждом вызове функции она будет одна и та же переменная. Вместо печати звёздочек пишем конструкцию s=s+1.
В основной части программы перед первым запуском функции переменной s присваиваем 0.
Программа может немного медленно работать из-за большой глубины рекурсии, но через минуту выведет число 96631265.