Перед тем как приступить конкретно к разбору этого задания, хотелось бы сказать несколько слов о рекурсии. Короче говоря, рекурсия возникает при вызове функцией саму себя. Возможно для кого-то сложно в это вникнуть, поэтому давайте рассмотрим рекурсию на примере. На том же питон-туторе была задачка про числа Фибоначчи, ее предлагают решить именно через рекурсию, а не через циклы. (Числа Фибоначчи — это элементы бесконечной числовой последовательности: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …, в которой каждое последующее число равно сумме двух предыдущих.).
Ниже представлена рекурсивная функция, которая считает n-ое число из последовательности Фибоначчи:
def fib(n):
if n == 1 or n == 2:
return 1
else:
return fib(n - 1) + fib(n - 2)
Рассмотрим работу этой функции подробно на примере подсчета значения 5 числа из последовательности Фибоначчи. Вызываем fib(5), смотрим на 2 строку функции, наша n=5, следовательно условие на 2 строке не выполнится и мы перейдем к else. Что видим на 5 строчке кода, мы возвращаем сумму двух значений от этой же функции, только передав ей другие числа. Первая вызов функции, который встречается в выражении, это fib(n-1), fib(5-1) а точнее fib(4).
Тут все аналогично тому что было с fib(5), только теперь мы дойдем до 5 строчки и вызовем соответственно fib(3)
А вот тут внимание, мы также доходим до 5 строчки, n=3. Следовательно выражение которое на 5 строчке, будет выглядеть так: fib(2)+fib(1)
Опять же, первой встречается вызов функции fib(2), следовательно она будет вызвана первой, но в ней, дело не дойдет до 5 строчке, так как выполнится условие (n == 1 or n == 2), n-ка же у нас двум равна , а что стоит под if-ом? return 1. Значит эта функция закончит свою работу и вернет число 1, мы поднимаемся на уровень выше, обратно в формулу fib(2)+fib(1), только вместо fib(2) будет стоять единичка, то-есть выражение превращается в 1+fib(1). Теперь передвигаемся к вызову fib(1), тут все будет также как с fib(2), выполнится условие со 2 строчки и функция вернет тоже единичку. Выражение 1+fib(1) превращается в 1+1, а это выражение равно двум. Получается вот это вот выражение fib(2)+fib(1), которое мы встретили внутри функции fib(3) будет равно двум.
Так как fib(3) было посчитано, функция возвращает двоечку в выражение fib(3)+fib(2), которое встретилось в функции fib(4). Выражение превращается в 2+fib(2). Вызывается функция fib(2), ее значение равно единице, следовательно fib(3)+fib(2) = 2+1 = 3, то есть значение которое вернет нам fib(4) будет тройка.
И вот мы вернулись обратно в fib(5). Там нам встретилось выражение fib(4)+fib(3). fib(4) уже посчитано и оно равно 3. Программе останется вызвать fib(3) , посчитать его значение, подставить в выражение и вернуть новое значение. В результате получим fib(5)=5.
Надеюсь по примеру было понятно как работают рекурсивные алгоритмы, а теперь приступим к разбору 11 задания. На самом деле оно решается, как говорится «в лоб» там может быть 3 типа задания и для каждого типа свой алгоритм решения.
Первый тип на тему «Алгоритмы, опирающиеся на несколько предыдущих значений»
Как я сказал выше, все задания решаются по одному алгоритму, поэтому я из каждого типа, возьму рандомный примерчик, напишу подробное его решение и думаю, этого будет достаточно, вам останется всего лишь набить руку, порешать как можно больше 11 номеров, чтоб этот номер не занимал у вас больше минуты на экзамене.
Итак, смотрим на задание
Берем листок, переписываем начало: F(1), F(2), а дальше пишем F(3) и считаем это выражение подставляя за место n — 3, а за место F(1) и F(2) — 1 и 3 соответственно
Аналогично, доходим до нужного нам F(5)
Вот и получили ответ, легко, не так ли? 🙂
Второй тип на тему «Алгоритмы, опирающиеся на одно предыдущее значение»
Этот тип очень похож на первый, только здесь вычисления по-проще. Решается по той же схеме, что и первый тип
Третий тип на тему «Вызов рекурсивных процедур»
Вот это тип уже немного сложнее предыдущих. Здесь для удобства и точности придется строить дерево, на примере которого я показывал работу рекурсивной функции в числах Фибоначчи. Ну да ладно, сейчас разберемся. Вот пример, который будет решать сейчас:
Разберем сначала сам код (естественно на python). Обратим внимание, что при вызове функции, сразу выводится n на экран. Потом мы видим условие if n < 5 и если оно выполняется, то вызываем эту же функцию по очереди с n+1 и n+3 соответственно. Если условие не выполнится, то функция закончит свою работу и программа выйдет из нее.
Наша задача найти сумму всех чисел, которые будут напечатаны при вызове функции F(1). Начнем строить дерево, и в отдельно место будет записывать числа, которые у нас будут выводиться на протяжении всей программы. Вызвалась функция F(1) и сразу вывелось число 1
Дальше идут вызовы функций F(n+1) и F(n+3) . Так как F(n+1) стоит первее, следовательно она и будет вызвана первая, и только потом программа вернется к F(n+3) (помните, этот порядок очень важен, позже объясню почему). Переходим в F(n+1) то есть в F(2) так как n=1. Рисуем дальше дерево и не забываем о print(n), двоечка будет выведена на экран.
В F(2) мы вызовем F(3) и F(5), но сначала F(3)
В F(3) вызовем F(4) и F(6)
А теперь внимание, в F(4) мы вызовем F(5) и F(7), но когда вызовется сначала та же F(5), не забываем о том что число 5 выведется на экран, при n=5 не выполнится условие n<5. Следовательно мы из F(4) погрузимся в F(5), выведем число 5 на экран и сразу же выйдем из этой функции обратно в F(4). Дальше после вызова F(5) идет вызов F(7), та будет такая же история, ведь 7>5
Вот и F(4) закончила свою работу, возвращаемся в F(3). Там после вызова F(4) идет вызов F(6). Опять же, 6>5. Следовательно при вызове F(6) только выведется число 6 на экран и больше ничего не произойдет, условие же не выполнится 🙂
Возвращаемся в F(2), из нее вызывается F(5)
Вот мы и оказались в F(1). После вызова F(2) из нее, следует вызов F(4)
Из F(4) вызываются F(5) и F(7), которые дальше ничего не вызывают, поэтому в консоль выведется еще сначала 5, а потом 7 и на этом программа закончит свою работу
По нашей задаче осталось посчитать сумму всех чисел, которые были выведены на экран, и эта сумма будет равна 49, следовательно ответ: 49.
А теперь о том, почему порядок очень важен, его как бы стоит отрабатывать, строить деревья эти и следить за порядком. Ибо встречаются задачи, типа напишите что выведет программа, а не напишите сумму всех чисел, которые выведет программа. Именно поэтому я советую отрабатывать все это сразу и никак иначе) Расписывайте каждый шаг программы, не придумывайте ничего своего.
На этом разбор 11 задачи закончен, надеюсь вам поможет эта статья разобраться в решении этого номера, если вдруг были какие-либо вопросы 🙂
Спасибо