Рекурсия. Практика ЕГЭ2. Задания 16

1.

Практика ЕГЭ. Рекурсия

2.

Задания 16
Нам уже дано описание рекурсивного алгоритма.
Остается только его написать.

3.

Запуск кода

4.

Рекурсивный перебор

5.

Объяснение
• Допустим n = 4. Посмотрим
на какое-то состояние
depth = n-1. Мы можем
заметить, что тут всего два
варианта: либо мы
добавляем в конец 0, либо
мы добавляем в конец 1

6.

Объяснение
• Если мы посмотрим на
состояние depth = n-2, мы
заметим, что у нас так же
всего 2 варианта: либо
добавить в конец 0, либо 1.
Поэтому мы рекурсивно
можем запускать программу
сначала для строки где мы
добавили 0, потом для строки
где мы добавили 1.