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

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

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

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

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

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

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

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

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

Задача 1#6315

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

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

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

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

При вызове $F (0)$ программа ничего не выведет. Пропишем весь алгоритм, начиная с единицы:

$F(1) → 1F (0)F(0) =$ $1F (2) → 2F (1)F (1) =$ $211F (3) → 3F (2)F(2) =$ $3211211F (4) → 4F (3)F (3) = 432112113211211$

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

Ответ: 432112113211211

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

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

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

Задача 2#6321

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

def f(n):
    if n < 6:
        print(n)
        f(n + 3)
        f(n + 2)
print(f(1))

Определите сумму всех чисел, которые будут выведены на экран при вызове функции $f (1 )$ .

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

Перепишем программу и запустим её. На экране появятся следующие числа: $1$ , $4$ , $3$ , $5$ . Посчитаем их сумму: $1 + 4 + 3 + 5 = 13$ . Это и будет ответ на задачу.

Ответ: 13

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

Задача 3#6322

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

def f(n):
    if n < 9:
        f(n + 5)
        f(n + 2)
        print(n)
print(f(1))

Определите сумму всех чисел, которые будут выведены на экран при вызове функции $f (1 )$ .

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

Перепишем программу и запустим её. На экране появятся следующие числа: $8$ , $6$ , $8$ , $7$ , $5$ , $3$ , $1$ . Посчитаем их сумму: $8 + 6 + 8 + 7 + 5 + 3 + 1 = 38$ . Это и будет ответ на задачу.

Ответ: 38

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

Задача 4#6323

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

def f(n):
    if n < 10:
        f(n + 6)
        f(n + 3)
        print(n)
print(f(1))

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

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

Перепишем программу и запустим её. На экране появятся следующие числа: $7,7,4,1$ .

$7741$ и будет ответом на задачу.

Ответ: 7741

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

Задача 5#6324

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

def f(n):
    if n < 10:
        f(n + 6)
        f(n + 3)
        print(n)
print(f(1))

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

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

Перепишем программу и запустим её. На экране появятся следующие числа: $8, 7,6,8,8,7,6,5,4, 3$ .

$8768876543$ и будет ответом на задачу.

Ответ: 8768876543

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

Задача 6#6325

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

def f(n):
    if n < 9:
        f(n * 3)
        f(n * 2)
        f(n + 1)
        print(n)
        print(n - 1)
print(f(4))

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

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

Перепишем программу и запустим её. На экране появятся следующие числа: $8,7, 8,7,7,6,6,5,5,4,4, 3$ .

$878776655443$ и будет ответом на задачу.

Ответ: 878776655443

Курсы

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

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

Задача 7#6326

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

def f(n):
    if n < 9:
        print(n * 2)
        f(n * 3)
        f(n * 2)
        f(n + 1)
        print(n)
        print(n - 1)
print(f(6))

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

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

Перепишем программу и запустим её. На экране появятся следующие числа: $12, 14,16,8,7,7,6, 6,5$ .

$121416877665$ и будет ответом на задачу.

Ответ: 121416877665

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

Задача 8#6812

Ниже на трех языках программирования записана рекурсивная функция (процедура) $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 | F (n − 1) | F (n − 1); | | begin | F (n∕∕2) | F (n∕2 ); | | F (n − 1); | print(n) | printf("%d ", n); | | F(n div 2); | | } | | writeln(n); | |} | | | | | | end; | | | -end.-----------------------------------------------------------|

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

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

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

С помощью стрелочки $→$ обозначим печать символа на экране.Рассмотрим последовательно, что будет выводится на экран, начиная с $F (3)$ :

$F(3) →$

$→ F (2) → ∘$ (От данного значения нет вывода числа на экран);

$→ F (1) → ∘$ (От данного значения нет вывода числа на экран);

$→ n → 3$ (Выводится текущее значение $n$ ).

$F(4) →$

$→ F (3) → 3$ (Выводится число, которое было получено от $F (3)$ в предыдущем шаге);

$→ F (2) → ∘$ (От данного значения нет вывода числа на экран);

$→ n → 4$ (Выводится текущее значение $n$ ).

$F(5) →$

$→ F (4) → 34$ (Выводится число, которое было получено от $F(4)$ в предыдущем шаге);

$→ F (2) → ∘$ (От данного значения нет вывода числа на экран);

$→ n → 5$ (Выводится текущее значение $n$ ).

$F(6) →$

$→ F (5) → 345$ (Выводится число, которое было получено от $F(5)$ в предыдущем шаге);

$→ F (3) → 3$ (Выводится число, которое было получено от $F (3)$ );

$→ n → 6$ (Выводится текущее значение $n$ ).

Следовательно, итоговая последовательность $→ 34536$ .

Ответ: 34536

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

Задача 9#7470

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

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

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

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

При вызове $F (0)$ программа ничего не выведет. Пропишем весь алгоритм, начиная с единицы:

$F(1) → F (0 )1F (0) = 1F (2) → F (1)2F (1) = 121F (3) → F (2)3F (2) = 1213121F (4) → F(3)4F (3) = 121312141213121$

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

Ответ: 26

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

Задача 10#7471

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

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

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

При вызове $F (0)$ программа ничего не выведет. Пропишем весь алгоритм, начиная с единицы:
$F (1) → F (0)F (0)1 = 1F (2) → F (1)F(1)2 = 112F (3 ) → F (2)F(2)3 = 1121123F (4) → F (3)F (3)4 = 112112311211234$

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

Ответ: 112112311211234

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

Задача 11#7472

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

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

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

При вызове $F (0)$ и $F (− 1)$ программа ничего не выведет. Пропишем весь алгоритм, начиная с единицы:
$F (1) → F (0)F (− 1 )1 = 1F(2) → F (1 )F (0)2 = 12F (3) → F(2)F (1)3 = 1213F (4) → F(3)F (2)4 = 1213124$

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

Ответ: 1213124

Интенсивы

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

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

Задача 12#7473

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

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

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

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

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

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

Ответ: 2342523

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

Задача 13#7474

Ниже на трёх языках программирования записан рекурсивный алгоритм 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 − 1) | { | begin | | F (n − 2) | cout < < n; | writeln(n); | | | F (n − 1); | F (n − 1); | | | F (n − 2); | F (n − 2) | | | | | | | } |end | ----------------}----------------end-----------------------

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

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

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

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

Ответ: 21

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

Задача 14#7475

Ниже на трёх языках программирования записан рекурсивный алгоритм 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 − 2) | { | begin | | print(n) | cout < < n; | writeln(n); | | | F (n − 2); | F (n − 2); | | | cout < < n; | writeln(n); | | | | | | | } |end | ----------------}----------------end-----------------------

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

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

При вызове $F (0)$ и $F (1 )$ программа ничего не выведет. Пропишем весь алгоритм, начиная с $F (2)$ :
$F (2) → 2F (0)2 = 22F (3) → 3F (1 )3 = 33F (4 ) → 4F (2)4 = 4224F (5) → 5F(3)5 = 5335F (6 ) → 6F (4)6 = 642246$

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

Ответ: 642246

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

Задача 15#7476

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

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

Определите сколько знаков выведет программа при вызове функции $F(6)$ ?

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

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

Всего программа вывела $7$ знаков. Это - ответ на вопрос задачи.

Ответ: 7

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

Задача 16#7477

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

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

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

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

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

Ответ: 41213121

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

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

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

Задача 17#7478

Ниже на трёх языках программирования записан рекурсивный алгоритм 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); | | F (n − 1) | cout < < n; | writeln(n); | | | F (n − 2); | F (n − 2); | | | | | | | F (n − 1); | F (n − 1); | | | } |end | ----------------}----------------end-----------------------

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

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

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

Ответ: 25324232

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

Задача 18#7479

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

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

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

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

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

Ответ: 23252432

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

Задача 19#7480

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

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

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

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

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

Ответ: 22322345

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

Задача 20#7481

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

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

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

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

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

Ответ: 3246

Предыдущий раздел

Следующий раздел