Двенадцатое занятие углублённого курса: база и шаг, стек вызовов, печать на спуске и подъёме, фракталы и дерево вызовов, функция по формуле (задание 16 ЕГЭ), три ошибки рекурсии; три программы из рекурсивных функций — уроки 23–24 плана
Рекурсивная функция зовёт сама себя. База — случай, где ответ даётся сразу, без вызова себя. Шаг — та же задача, но меньше: digsum(n // 10) + n % 10. Шаг обязан вести к базе.
Незаконченные вызовы ждут в стеке, у каждого своё n. Ответ отдаётся тому, кто лежит ниже. Глубина — сколько вызовов ждут одновременно; предел Python — около тысячи, дальше RecursionError.
print до вызова — на спуске, сверху вниз; print после вызова — на подъёме, в обратном порядке. Остатки n % 2, напечатанные после вызова p(n // 2), дают двоичную запись по порядку.
Два вызова в теле — дерево, как у фрактала: 1 + 2 + 4 + … вызовов. Считаются все вызовы, и те, что сразу упираются в базу.
Случаи формулы — ветки if, база — первый случай. Две функции могут звать друг друга. На бумаге считать снизу вверх таблицей: F(1), F(2), F(3)…
Нет базы — RecursionError. Шаг мимо базы (через два из нечётного) — то же. Забыт return — наверх уходит None и TypeError на None + n.
Двенадцатое занятие углублённого курса: база и шаг, стек вызовов, печать на спуске и подъёме, фракталы и дерево вызовов, функция по формуле (задание 16 ЕГЭ), три ошибки рекурсии; три программы из рекурсивных функций — уроки 23–24 плана
Рекурсивная функция зовёт сама себя. База — случай, где ответ даётся сразу, без вызова себя. Шаг — та же задача, но меньше: digsum(n // 10) + n % 10. Шаг обязан вести к базе.
Незаконченные вызовы ждут в стеке, у каждого своё n. Ответ отдаётся тому, кто лежит ниже. Глубина — сколько вызовов ждут одновременно; предел Python — около тысячи, дальше RecursionError.
print до вызова — на спуске, сверху вниз; print после вызова — на подъёме, в обратном порядке. Остатки n % 2, напечатанные после вызова p(n // 2), дают двоичную запись по порядку.
Два вызова в теле — дерево, как у фрактала: 1 + 2 + 4 + … вызовов. Считаются все вызовы, и те, что сразу упираются в базу.
Случаи формулы — ветки if, база — первый случай. Две функции могут звать друг друга. На бумаге считать снизу вверх таблицей: F(1), F(2), F(3)…
Нет базы — RecursionError. Шаг мимо базы (через два из нечётного) — то же. Забыт return — наверх уходит None и TypeError на None + n.