Теория для 11 задания ЕГЭ по информатике
Для начала разберёмся с понятием Рекурсия.
Рекурсия — вызов функции внутри самой себя.
Давайте разберёмся на примере. Предположим, вы где-то работаете и вам каждый день платят по 1000 рублей. Вы хотите узнать, сколько у вас сейчас денег. Давайте попробуем их посчитать через рекурсию.
Сегодняшняя сумма ваших денег — это вчерашняя сумма, увеличенная на 1000 рублей.
А вчерашняя сумма денег — это позавчерашняя сумма, увеличенная на 1000 рублей.
И так можно продолжать до бесконечности. Ситуацию можно описать формулой:
F(n) = F(n-1)+1000, где F(n) — сумма денег в n-ый день, а F(n-1) — сумма денег в предыдущий n-1-ый день. Такая формула называется рекуррентной.
Но так мы можем считать до бесконечности. Сумма, которая была у нас 451 день назад = сумме, которая была 452 назад, увеличенной на 1000. Именно поэтому нам необходимо условие выхода из рекурсии:
Предположим, что в 1-ый день у нас было 0 рублей. А сейчас 100-ый день, тогда если n > 1, то нашу сумму можно посчитать по формуле
F(n) = F(n-1)+1000,
а если n = 1, то
F(n) = 0 — это и есть условие выхода из рекурсии.
В виде кода (язык Python) это можно записать как:
def f(n):
ᅠif n > 1:
ᅠᅠreturn f(n-1)+1000
ᅠelse:
ᅠᅠreturn 0
Практика
Пример
На рисунке записан рекурсивный алгоритм F. Чему равна сумма чисел, напечатанных на экране при выполнении вызова F(4)?
Решение
Обратим внимание, что вывод значения на экран происходит в тот момент, когда запускается наша процедура. Следовательно, как только мы вызвали F(4), на экране появилось первое число. Консоль вывода будет выглядеть так: | 4
Далее проверяется условие n > 1. 4 явно больше 1, значит заходим внутрь условного оператора, оказываемся на строчке f(n-1). Эта строчка запускает процедуру f(n-1). Важный момент: сейчас текущая процедура f(n) встала на паузу и ждёт, пока процедура f(n-1) полностью завершит свою работу. Это как в Марио попасть с основного уровня на бонусный. Пока мы на бонусном уровне, основной уровень стоит на паузе.
Схему проще всего представлять в виде дерева:
Теперь запустилась процедура F(3). Сразу же в консоль отправляется число «3». Теперь в консоли мы наблюдаем:
| 4 3
Далее проверяется условие n > 1. 3 больше, чем 1, значит вновь оказываемся на строчке f(n-1) и запускаем f(2):
F(2) выводит на экран число «2»:
| 4 3 2
2 > 1, значит F(2) запускает F(n-1), то есть F(1):
F(1) выводит на экран число «1»:
| 4 3 2 1
Проверка условия n > 1 даёт нам False. 1 не больше, чем 1. Значит процедура F(1) завершает свою работу. Возвращаемся в процедуру F(2). Там мы остановились на строчке F(n-1), которая только что успешно завершила свою работу. Переходит к следующей строчке: F(n-2), которая вызовет F(0):
F(0) выведет на экран 0 и тут же завершит свою работу, не пройдя условие n > 1:
| 4 3 2 1 0
Больше в F(2) делать нечего, она тоже завершает свою работу. Мы возвращаемся в F(3), где остановились на строчке F(n-1). Теперь переходим к строчке F(n-2) и вызываем F(1):
Мы уже вызывали F(1) ранее, но сейчас он вызывается заново, выводит на экран «1» и завершается, не пройдя условие n > 1:
| 4 3 2 1 0 1
Возвращаемся в F(3), она завершила свою работу. Теперь возвращаемся в самое начало — процедуру F(4). Напоминаю, что в ней мы остановились на строчке F(n-1). Теперь, когда она полностью завершила свою работу, мы приступаем к следующей строке F(n-2) и вызываем F(2). Ранее мы уже вызывали F(2) и знаем, что дерево выглядеть будет так:
И выведет поочередно «2» «1» «0»:
| 4 3 2 1 0 1 2 1 0
После чего все процедуры завершат свою работу, а значит и программа завершит свою работу. Осталось сложить числа, выведенные на экран, согласно условию:
4+3+2+1+0+1+2+1+0=14
Ответ: 14