Тема 16. Рекурсия

16.01 Одна функция

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела рекурсия

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 21#7482Максимум баллов за задание: 1

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|----------------|-------------------------| |Python--------|C-+-+-----------|P-ascal------------------| |defF (n) : |voidF (intn ) |procedureF (n : integer );| | ifn > 1 : |{ | begin | | | | | | F (n − 3) | if(n > 1) | if n > 1then | | print(n) | { | begin | | F (n − 2) | F (n − 3); | F (n − 3); | | | cout < < n; | writeln(n); | | | F (n − 2); | F (n − 2); | | | | | | | } |end | ----------------}----------------end-----------------------

Определите, что выведет программа при вызове функции F(7)? Цифры запишите в той последовательности, в которой они выводятся.

Показать ответ и решение

При вызове $F (− 1)$ , $F (0)$ и $F (1)$ программа ничего не выведет. Пропишем весь алгоритм, начиная с $F (2)$ :
$F (2) → F (− 1)2F (0) = 2F(3) → F (0 )3F (1) = 3F (4) → F(1)4F (2) = 42F (5) → F (2)5F (3) = 253F (6) → F (3)6F (4) = 3642F (7) → F$

Программа вывела $427253$ , это - ответ на вопрос задачи.

Ответ: 427253

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 22#7483Максимум баллов за задание: 1

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|----------------|-------------------------| |Python--------|C-+-+-----------|P-ascal------------------| |defF (n) : |voidF (intn ) |procedureF (n : integer );| | ifn > 1 : |{ | begin | | | | | | print(n) | if(n > 1) | if n > 1then | | F (n − 3) | { | begin | | F (n − 2) | cout < < n; | writeln(n); | | | F (n − 3); | F (n − 3); | | | F (n − 2); | F (n − 2); | | | | | | | } |end | ----------------}----------------end-----------------------

Показать ответ и решение

def f(n):
    if n > 1:
        print(n)
        f(n - 3)
        f(n - 2)
print(f(7))

Ответ: 742523

Ошибка.
Попробуйте повторить позже

Задача 23#7484Максимум баллов за задание: 1

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|----------------|-------------------------| |Python--------|C-+-+-----------|P-ascal------------------| |defF (n) : |voidF (intn ) |procedureF (n : integer );| | print(n) |{ | begin | | | | | | ifn > 4 : | cout < < n; | writeln (n); | | print(n) | if(n > 4) | ifn > 4then | | F (n − 3) | { | begin | | F (n − 2) | cout < < n; | writeln(n); | | | F (n − 3); | F (n − 3); | | | | | | | F (n − 2); | F (n − 2); | | | } |end | ----------------}----------------end-----------------------

Показать ответ и решение

При вызове $F (2)$ программа выведет 2, при вызове $F (3)$ программа выведет 3, при вызове $F (4)$ программа выведет 4. Пропишем весь алгоритм, начиная с $F (5)$ :
$F (5) → 55F (2)F (3) = 5523F (6) → 66F (3 )F (4) = 6634F (7) → 77F (4)F(5) = 7745523$

Программа вывела $7745523$ , это - ответ на вопрос задачи.

Ответ: 7745523

Ошибка.
Попробуйте повторить позже

Задача 24#7485Максимум баллов за задание: 1

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|-----------------------|--------------------------| |P ython |C + + |P ascal | |def-F-(n-) :---|voidF-(intn)-----------|procedureF--(n-: integer);| | | | | | print (n ) |{ | begin | | if n < 6 : | cout < < n < < endl;| writeln(n ); | | F(n + 2 )| if (n < 6){ | if n < 6then | | F(n + 4 )| F (n + 2); | begin | | | F (n + 4); | F (n + 2); | | | | | | | } | F (n + 4) | | |} | end | ----------------------------------------end-----------------------|

Определите, что выведет программа при вызове функции F(2)? Цифры запишите в той последовательности, в которой они выводятся.

Показать ответ и решение

При вызове $F (n ≥ 6)$ программа выведет $n$ . Пропишем весь алгоритм, начиная с конца:
$F (6) → 6 = 6F(5) → 5F (7)F(9) = 579F (4) → 4F (6 )F (8) = 468F (3) → 3F (5 )F (7) = 35797F (2) → 2F (4)F(6) = 24686$

$24686$ И будет ответом на вопрос задачи.

Ответ: 24686

Ошибка.
Попробуйте повторить позже

Задача 25#7486Максимум баллов за задание: 1

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|-----------------------|--------------------------| |P ython |C + + |P ascal | |def-F-(n-) :---|voidF-(intn)-----------|procedureF--(n-: integer);| | | | | | print (n ) |{ | begin | | if n < 5 : | cout < < n < < endl;| writeln(n ); | | F(n + 3 )| if (n < 5){ | if n < 5then | | F(n ∗ 2) | F (n + 3); | begin | | | F (n ∗ 2); | F (n + 3); | | | | | | | } | F (n ∗ 2) | | |} | end | ----------------------------------------end-----------------------|

Определите, что выведет программа при вызове функции F(1)? Цифры запишите в той последовательности, в которой они выводятся.

Показать ответ и решение

При вызове $F (n ≥ 5)$ программа выведет $n$ . Пропишем весь алгоритм, начиная с конца:
$F (5) → 5 = 5F(4) → 4F (7)F(8) = 478F (3) → 3F (6 )F (6) = 366F (2) → 2F (5 )F (4) = 25478F (1) → 1F (4)F(2) = 147825478$

$147825478$ И будет ответом на вопрос задачи.

Ответ: 147825478

Ошибка.
Попробуйте повторить позже

Задача 26#7487Максимум баллов за задание: 1

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|-----------------------|--------------------------| |P ython |C + + |P ascal | |def-F-(n-) :---|voidF-(intn)-----------|procedureF--(n-: integer);| | | | | | print (n ) |{ | begin | | if n < 5 : | cout < < n < < endl;| writeln(n ); | | F(n + 4 )| if (n < 5){ | if n < 5then | | F(n + 5 )| F (n + 4); | begin | | | F (n + 5); | F (n + 4); | | | | | | | } | F (n + 5) | | |} | end | ----------------------------------------end-----------------------|

Показать ответ и решение

При вызове $F (n ≥ 5)$ программа выведет $n$ . Пропишем весь алгоритм, начиная с конца:
$F (5) → 5 = 5F(4) → 4F (8)F(9) = 489F (3) → 3F (7 )F (8) = 378F (2) → 2F (6 )F (7) = 267F (1) → 1F(5)F (6) = 156$

$156$ И будет ответом на вопрос задачи.

Ответ: 156

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 27#7488Максимум баллов за задание: 1

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|-----------------------|--------------------------| |P ython |C + + |P ascal | |def-F-(n-) :---|voidF-(intn)-----------|procedureF--(n-: integer);| | | | | | print (n ) |{ | begin | | if n < 7 : | cout < < n < < endl;| writeln(n ); | | F(n ∗ 2) | if (n < 7){ | if n < 7then | | F(n + 2 )| F (n ∗ 2); | begin | | | F (n + 2); | F (n ∗ 2); | | | | | | | } | F (n + 2) | | |} | end | ----------------------------------------end-----------------------|

Показать ответ и решение

При вызове $F (n ≥ 7)$ программа выведет $n$ . Пропишем весь алгоритм, начиная с конца:
$F (7) → 7 = 7F(6) → 6F (12)F(8) = 6128F (5 ) → 5F (10)F (7 ) = 5107F (4) → 4F (8)F (6 ) = 486128F (3) → 3F (6)F (5) = 361285107F (2 ) → 2F (4�$

$2486128486128$ И будет ответом на вопрос задачи.

Ответ: 2486128486128

Ошибка.
Попробуйте повторить позже

Задача 28#7489Максимум баллов за задание: 1

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|-----------------------|--------------------------| |P ython |C + + |P ascal | |def-F-(n-) :---|voidF-(intn)-----------|procedureF--(n-: integer);| | | | | | if n < 7 : |{ | begin | | print(n) | if (n < 7){ | if n < 7then | | F(n ∗ 2) | cout < < n < < endl;| begin | | F(n + 2 )| F (n ∗ 2); | writeln(n ); | | | F (n + 2); | F (n ∗ 2); | | | | | | | } | F (n + 2) | | |} | end | ----------------------------------------end-----------------------|

Определите сумму цифр при вызове функции F(1)?

Показать ответ и решение

При вызове $F (n ≥ 7)$ программа выведет $N OT HIN G$ . Пропишем весь алгоритм, начиная с конца:
$F (7) → N OT HIN GF (6 ) → 6F (12)F (8) = 6F(5) → 5F (10)F(7) = 5F (4) → 4F(8)F (6) = 46F (3) → 3F (6)F (5) = 365F (2) → 2F (4)F (4)$

$1 + 2 + 4 + 6 + 4 + 6 + 3 + 6 + 5 = 37$ и будет ответом на вопрос задачи.

Ответ: 37

Ошибка.
Попробуйте повторить позже

Задача 29#7490Максимум баллов за задание: 1

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|-----------------------|--------------------------| |P ython |C + + |P ascal | |def-F-(n-) :---|voidF-(intn)-----------|procedureF--(n-: integer);| | | | | | if n < 6 : |{ | begin | | F(n + 1 )| if (n < 6){ | if n < 6then | | print(n) | F (n + 1); | begin | | F(n + 2 )| cout < < n < < endl;| F (n + 1); | | | F (n + 2); | writeln(n ); | | | | | | | } | F (n + 2) | | |} | end | ----------------------------------------end-----------------------|

Определите сумму цифр при вызове функции F(2)?

Показать ответ и решение

При вызове $F (n ≥ 6)$ программа выведет $N OT HIN G$ . Пропишем весь алгоритм, начиная с конца:
$F (6) → N OT HIN GF (5 ) → F (6)5F (7 ) = 5F (4) → F(5)4F (6) = 54F (3) → F (4)3F (5) = 5435F (2) → F (3)2F (4) = 5435254$

$5 + 4 + 3 + 5 + 2 + 5 + 4 = 28$ и будет ответом на вопрос задачи.

Ответ: 28

Ошибка.
Попробуйте повторить позже

Задача 30#7491Максимум баллов за задание: 1

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|-----------------------|--------------------------| |P ython |C + + |P ascal | |def-F-(n-) :---|voidF-(intn)-----------|procedureF--(n-: integer);| | | | | | if n < 10 : |{ | begin | | F(n + 3 )| if (n < 10){ | if n < 10then | | print(n) | F (n + 3); | begin | | F(n + 3 )| cout < < n < < endl;| F (n + 3); | | | F (n + 3); | writeln(n ); | | | | | | | } | F (n + 3) | | |} | end | ----------------------------------------end-----------------------|

Определите, что выведет программа при вызове функции F(3)? Цифры запишите в той последовательности, в которой они выводятся.

Показать ответ и решение

При вызове $F (n ≥ 10)$ программа выведет $N OT HIN G$ . Пропишем весь алгоритм, начиная с конца:
$F (10) → N OT HIN GF (9) → F (12)9F (12) = 9F (8 ) → F (11)8F (11) = 8F (7 ) → F (10)7F (10 ) = 7F(6) → F (9 )6F (9) = 969F (5) → F (8)5F (8$

$9693969$ и будет ответом на вопрос задачи.

Ответ: 9693969

Ошибка.
Попробуйте повторить позже

Задача 31#7492Максимум баллов за задание: 1

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|-----------------------|-------------------------| |P ython |C + + |P ascal | |def-F-(n) :---|voidF-(intn)-----------|procedureF--(n-: integer); | | | | | if n < 5 : |{ | begin | | print(n) | if(n < 5){ | if n < 5then | | F (n ∗ 2)| cout < < n < < endl; | begin | | F (n ∗ 2)| F(n ∗ 2); | writeln(n); | | | F(n ∗ 2); | F(n ∗ 2); | | | | | | | } | F(n ∗ 2) | | |} | end | ----------------------------------------end-----------------------

Показать ответ и решение

При вызове $F (n ≥ 5)$ программа выведет $N OT HIN G$ . Пропишем весь алгоритм, начиная с конца:
$F (5) → N OT HIN GF (4 ) → 4F (8)F (8 ) = 4F (3) → 3F (6 )F (6) = 3F (2) → 2F (4)F (4) = 244F (1) → 1F (2)F (2) = 1244244$

$1244244$ и будет ответом на вопрос задачи.

Ответ: 1244244

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 32#7493Максимум баллов за задание: 1

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|-----------------------|--------------------------| |P ython |C + + |P ascal | |def-F-(n-) :---|voidF-(intn)-----------|procedureF--(n-: integer);| | | | | | if n < 9 : |{ | begin | | print(n) | if (n < 9){ | if n < 9then | | F(n ∗ 3) | cout < < n < < endl;| begin | | F(n ∗ 2) | F (n ∗ 3); | writeln(n ); | | F(n + 1 )| F (n ∗ 2); | F (n ∗ 3); | | | | | | | F (n + 1); | F (n ∗ 2); | | | } | F (n + 1) | | |} | end | | | |end | ------------------------------------------------------------------

Показать ответ и решение

При вызове $F (n ≥ 9)$ программа выведет $N OT HIN G$ . Пропишем весь алгоритм, начиная с конца:
$F (9) → N OT HIN GF (8 ) → 8F (24)F (16)F(9) = 8F (7) → 7F(21 )F (14)F (8) = 78F (6) → 6F (18)F (12)F (7 ) = 678F (5 ) → 5F (15)F (10 )F&#x$

$3678485678$ и будет ответом на вопрос задачи.

Ответ: 3678485678

Ошибка.
Попробуйте повторить позже

Задача 33#7494Максимум баллов за задание: 1

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|-----------------------|--------------------------| |P ython |C + + |P ascal | |def-F-(n-) :---|voidF-(intn)-----------|procedureF--(n-: integer);| | | | | | if n < 9 : |{ | begin | | F(n ∗ 3) | if (n < 9){ | if n < 9then | | print(n) | F (n ∗ 3); | begin | | F(n ∗ 2) | cout < < n < < endl;| F (n ∗ 3); | | F(n + 1 )| F (n ∗ 2); | writeln(n ); | | | | | | | F (n + 1); | F (n ∗ 2); | | | } | F (n + 1) | | |} | end | | | |end | ------------------------------------------------------------------

Определите сумму цифр при вызове функции F(3)?

Показать ответ и решение

При вызове $F (n ≥ 9)$ программа выведет $N OT HIN G$ . Пропишем весь алгоритм, начиная с конца:
$F (9) → N OT HIN GF (8 ) → F (24)8F (16)F(9) = 8F (7) → F(21)7F (14)F (8) = 78F (6) → F (18)6F (12)F (7 ) = 678F (5 ) → F (15)5F (10 )F&#x$

$3 + 6 + 7 + 8 + 4 + 8 + 5 + 6 + 7 + 8 = 62$ и будет ответом на вопрос задачи.

Ответ: 62

Ошибка.
Попробуйте повторить позже

Задача 34#7495Максимум баллов за задание: 1

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|--------------|-----------------------|--------------------------| |P ython |C + + |P ascal | |def-F-(n-) :---|voidF-(intn)-----------|procedureF--(n-: integer);| | | | | | if n < 9 : |{ | begin | | F(n ∗ 3) | if (n < 9){ | if n < 9then | | F(n ∗ 2) | F (n ∗ 3); | begin | | print(n) | F (n ∗ 2); | F (n ∗ 3); | | F(n + 1 )| cout < < n < < endl;| F (n ∗ 2); | | | | | | | F (n + 1); | writeln(n ); | | | } | F (n + 1) | | |} | end | | | |end | ------------------------------------------------------------------

Показать ответ и решение

При вызове $F (n ≥ 9)$ программа выведет $N OT HIN G$ . Пропишем весь алгоритм, начиная с конца:
$F (9) → N OT HIN GF (8 ) → F (24)F (16 )8F (9) = 8F (7) → F(21)F (14)7F (8) = 78F (6) → F (18)F (12)6F (7 ) = 678F (5 ) → F (15)F(10 )5F &#x$

$6783845678$ и будет ответом на вопрос задачи.

Ответ: 6783845678

Ошибка.
Попробуйте повторить позже

Задача 35#7496Максимум баллов за задание: 1

Ниже на трёх языках программирования записан рекурсивный алгоритм F.

|-----------------|---------------------------|-------------------------| |Python |C + + |P ascal | |defF-(n)-:-------|voidF-(intn)---------------|procedureF--(n :-integer); | | | | | ifn < 9 : |{ | begin | | F (n ∗ 3) | if(n < 9){ | ifn < 9then | | F (n ∗ 2) | F(n ∗ 3); | begin | | F (n + 1) | F(n ∗ 2); | F(n ∗ 3); | | print(n − 1) | F(n + 1); | F(n ∗ 2); | | | | | | | cout < < n − 1 < < endl; | F(n + 1) | | | } | writeln(n − 1); | | |} | end | | | |end | -------------------------------------------------------------------------

Показать ответ и решение

При вызове $F (n ≥ 9)$ программа выведет $N OT HIN G$ . Пропишем весь алгоритм, начиная с конца:
$F (9) → N OT HIN GF (8 ) → F (24)F (16 )F (9)7 = 7F (7) → F(21)F (14)F (8)6 = 76F (6) → F (18)F (12)F(7)5 = 765F (5 ) → F (15)F(10 )F$

$7657765432$ и будет ответом на вопрос задачи.

Ответ: 7657765432

Ошибка.
Попробуйте повторить позже

Задача 36#7606Максимум баллов за задание: 1

Ниже на трех языках программирования записана рекурсивная функция (процедура) $F$ .

|------------------------|---------------|------------------| |Pascal |Python |C | |procedure-F(n:-integer);-|def-F(n):------|void-F-(int-n){-----| | | | | |begin | if n > 2: | if (n > 2 ){ | | if n > 2 then | print(” ∗ ”) | printf(” ∗ ”);| | begin | F (n − 1) | F (n − 1); | | writeln (” ∗ ”); | F (n∕∕2 ) | F (n∕2); | | F (n − 1); | | } | | | | | | F (n div 2); | |} | | end; | | | -end.--------------------------------------------------------

Сколько символов « $∗$ » будет напечатано на экране при выполнении вызова $F(7)$ ?

Показать ответ и решение

Данная рекурсивная функция останавливается, если $n$ принимает значение 2 или меньше. Следовательно, начнем выполнение функции, когда $n = 3$ . С помощью стрелочки $→$ обозначим печать символа на экране.

При запуске $F (3)$ на экране появляется один символ « $∗$ ». Далее никакие функции не вызываются. $F (3) → ∗$ .

При запуске $F (4)$ на экране появляется один символ « $∗$ ». Далее вызываются функции $F (4 − 1 = 3)$ и $F (4∕2 = 2)$ . Так как $n > 2$ , то смотрим на $F(3)$ и добавляем количество символов от данной функции к количеству символов от $F (4)$ .

$F(3) → ∗$

$F(4) → ∗∗$ .

Далее действуем по тому же принципу, возвращаясь к предыдущим значениям и добавляя количество символов к текущему:

$F(3) → ∗$ ;

$F(4) → ∗∗$ ;

$F(5) → ∗ ∗ ∗$ . Т.к. $5 > 2$ печатется один символ « $∗$ » , а также вызывались функции $F (4)$ и $F (2)$ . Так как $n > 2$ , то взяли кол-во символов только от $F (4)$ .

$F(6) → ∗ ∗ ∗ ∗ ∗$ . Т.к. $6 > 2$ печатется один символ « $∗$ » , а также вызывались функции $F(5)$ и $F (3$ ). Того 5 символов.

$F(7) → ∗ ∗ ∗ ∗ ∗ ∗ ∗$ . Т.к. $7 > 2$ печатется один символ « $∗$ » , а также вызывались функции $F(6)$ и $F (3)$ . Того 7 символов.

Ответ: 7

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 37#7607Максимум баллов за задание: 1

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

Е СЛ И n > 4: print(*) F (n -2) F (n -3)

Сколько звездочек напечатает функция при выполнении вызова $F (9)$ ?

Показать ответ и решение

def f(n):
    if n > 4:
        return 1 + f(n - 2) + f(n - 3)
    else:
        return 0
print(f(9))

Ответ: 4

Ошибка.
Попробуйте повторить позже

Задача 38#7608Максимум баллов за задание: 1

Ниже на трех языках программирования записана рекурсивная функция (процедура) $F$ .

|------------------------|---------------|--------------------| |Pascal |Python |C | |procedure-F(n:-integer);|def-F(n-):-----|void-F-(int-n)-{------| | | | | |begin | print(n ) | printf(”%d ” ,n); | | write(n); | if n > 4: | if (n > 4 ) { | | if n > 4 then | F (n − 3) | F (n − 3); | | begin | F (n − 2) | F (n − 2); | | F(n − 3); | | } | | | | | | F(n − 2); | |} | | end; | | | -end.----------------------------------------------------------

Что выведет программа при вызове $F (7)$ ? В ответе запишите последовательность выведенных цифр слитно (без пробелов).

Показать ответ и решение

Рассмотрим последовательно, что будет выводится на экран, начиная с $F (1)$ . Пока $n ≤ 4$ другие функции вызываться не будут. С помощью стрелочки $→$ обозначим печать числа на экране.

$F(1) → 1$ ; $F (2 ) → 2$ ; $F (3) → 3$ ; $F (4) → 4$ .

Далее при $n > 4$ дополнительно будут вызываться функции. Мы будем возвращаться каждый раз к предыдущим значениям и добавлять числа в последовательность: