LANG·I Язык Глава 9 из 65
Задача внутри задачи
Головоломка 1883 года с легендой о конце света, снежинка с бесконечным периметром и папка, в которой папки. Всё это решает одна идея — функция, которая вызывает саму себя. Научимся её писать и, что труднее, ей доверять.
Язык
Опирается на: 05 · Свои слова 06 · Списки
Что вы унесёте из главы
- решать задачу, сводя её к такой же задаче поменьше: базовый случай и шаг
- понимать, что происходит со стеком вызовов, и почему рекурсия бывает слишком глубокой или слишком медленной
- обходить вложенные данные любой глубины — папки, JSON, списки в списках — и рисовать фракталы
Прошлая глава кончилась папкой с черновиками. Размер папки — это размеры файлов плюс размеры вложенных папок, а у тех свои вложенные, и сколько этажей вниз, заранее не скажешь. Вложенные циклы тут бессильны: на каждый этаж нужен свой цикл. Подсказка спрятана в самой задаче: чтобы узнать размер папки, нужно знать размеры папок поменьше, а это та же задача, только меньше.
К папкам мы вернёмся в середине главы, когда научимся этой подсказкой пользоваться. Сначала будет головоломка с легендой: вы решите её руками, потом тремя строками кода. Потом откроется художественная мастерская, где те же три строки рисуют деревья, снежинки и треугольники из треугольников. А началось всё с игрушки, которую в 1883 году продавали в Париже.
Париж, 1883. Легенда из коробки
Сколько осталось миру, зависит от числа ходов для 64 дисков. До него мы доберёмся, но начнём с маленькой башни.
Сначала руками
Перенесите башню из трёх дисков со стержня A на стержень C. Нажмите на стержень, чтобы взять его верхний диск, и на другой стержень, чтобы положить. Счётчик сравнит ваши ходы с наименьшим возможным числом.
Три диска решаются за семь ходов. С четырьмя станет труднее, с пятью — легко запутаться. Прежде чем читать дальше, сделайте ставку.
Брахманы делают один ход в секунду и не ошибаются. Сколько времени займут 64 диска?
Около 585 миллиардов лет. Каждый новый диск удваивает работу, и 64 удвоения дают $2^{64} - 1 = 18\,446\,744\,073\,709\,551\,615$ ходов. Возраст Вселенной — около 13,8 миллиарда лет, так что брахманам нужно больше сорока таких возрастов. Почему именно $2^{64} - 1$, мы докажем через пару разделов.
Возьмите башню из четырёх дисков и следите за самым большим. Когда-нибудь он должен переехать с A на C. В этот момент на нём ничего не лежит, и на C ничего нет, иначе он бы туда не лёг. Значит, все три диска поменьше стоят тогда на B, единственном оставшемся стержне, причём правильной башней. План складывается сам:
- перенести башню из трёх верхних дисков с A на B (C служит запасным);
- переложить самый большой диск с A на C;
- перенести башню из трёх дисков с B на C (запасным теперь служит A).
Первый и третий шаги — та же задача, только с тремя дисками вместо четырёх. А как перенести три? Точно так же: два на запасной, большой на место, два сверху. Два — один на запасной, второй на место, первый сверху. Один диск переносится одним ходом, без всяких планов. Включите «Решение» в головоломке и следите за планом рядом с башней: он растёт вглубь и сворачивается обратно.
Чтобы перенести башню из $n$ дисков, достаточно уметь переносить башню из $n - 1$ диска. Задача сводится к такой же задаче поменьше — и так до задачи, которая решается сразу.
Три строки
План записывается на Python почти дословно. Функция hanoi(n, source, target, spare) переносит башню из n дисков со стержня source на target, пользуясь запасным spare, и печатает каждый ход.
Функция вызывает сама себя. Такой приём называют рекурсией, от латинского recurrere — «возвращаться». Запустите ячейку, а потом нажмите в головоломке «Ходы из ячейки» — она проиграет ходы вашей программы. Поменяйте 3 на 5 или на 8, как в коробке Люка, и проверьте снова.
В рекурсивной функции всегда две части. Первая — базовый случай: задача настолько мала, что решается сразу. Здесь это башня из нуля дисков, на которую не нужно ни одного хода. Вторая — шаг: задача сводится к таким же, но меньше. Здесь башня из $n$ дисков сводится к двум башням из $n - 1$. Каждый вызов уменьшает $n$ на единицу, поэтому рано или поздно дело доходит до нуля, и рекурсия останавливается.
Нажмите «Шаги» под программой. В колонке кадров видно, как вызовы складываются стопкой: hanoi(3, …) зовёт hanoi(2, …), тот — hanoi(1, …), тот — hanoi(0, …), который сразу возвращается. У каждого кадра свои n, source, target и spare, поэтому вызовы не путают, кто куда что переносит.
Сколько ходов
Обозначим через $T(n)$ число ходов, которое делает наша функция для $n$ дисков. Базовый случай не делает ходов: $T(0) = 0$. Шаг делает две башни поменьше и один ход между ними: $T(n) = 2T(n-1) + 1$. Значит, $T(1) = 1$, $T(2) = 3$, $T(3) = 7$, $T(4) = 15$ — каждый раз на единицу меньше степени двойки.
Башню из $n$ дисков можно перенести за $2^n - 1$ ходов, и быстрее нельзя.
Докажем обе половины индукцией по $n$. База: для $n = 0$ нужно $0 = 2^0 - 1$ ходов.
Шаг. Пусть для $n - 1$ дисков утверждение верно. Наш план делает $(2^{n-1} - 1) + 1 + (2^{n-1} - 1) = 2^n - 1$ ходов — значит, столько хватает. Теперь любой способ. Самый большой диск должен хотя бы раз переехать. В момент его первого переезда остальные $n - 1$ дисков лежат на третьем стержне — не на том, откуда он уходит, и не на том, куда, — а собрать их там значит перенести башню из $n - 1$ дисков: по предположению, не меньше $2^{n-1} - 1$ ходов. В момент его последнего переезда они снова все на третьем стержне, и потом их нужно перенести на него — ещё не меньше $2^{n-1} - 1$. Вместе с ходом большого диска выходит не меньше $2^n - 1$.
Доказательство устроено так: проверили самый маленький случай, а для большого воспользовались тем, что для меньшего всё уже доказано. Это математическая индукция, которую в курсе математики объясняли на падающих костяшках домино. Индукция доказывает утверждение для $n$, опираясь на $n - 1$; рекурсия вычисляет ответ для $n$, опираясь на $n - 1$. Это одна мысль, высказанная дважды, и в обоих случаях без базы ничего не работает.
Осталось посчитать, сколько у мира времени.
Около 585 миллиардов лет. Миру по легенде Люка ничего не грозит: даже если брахманы начали в момент Большого взрыва, им осталось почти всё. Компьютеру, который делает миллиард ходов в секунду, понадобилось бы около 585 лет — те же цифры, только уже не миллиардов. Число $2^n - 1$ растёт так быстро, что никакая скорость его не догонит; об этом будет глава 13.
Как Python не теряется
В главе 5 мы видели, что каждый вызов функции получает свой кадр — рабочее место со своими переменными, — и кадры складываются в стек вызовов. Там же было сказано, почему подпрограммы EDSAC не могли звать сами себя: адрес возврата хранился в одном месте, и второй вызов затирал первый. У Python адрес возврата лежит в каждом кадре, поэтому функция может звать себя снова и снова, пока не упрётся в предел, о котором ниже, — и каждый вызов вернётся туда, откуда его позвали.
Проследим за стеком на самой классической рекурсивной функции. Факториал $n!$ — произведение чисел от 1 до $n$: $5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$. Но $5! = 5 \cdot 4!$, и вообще $n! = n \cdot (n-1)!$, а это готовый шаг рекурсии. Базовый случай — $0! = 1$ (так договорились, и так удобно: произведение пустого набора чисел равно единице).
Нажмите «Шаги» и проследите, что происходит с factorial(5). Он не может сразу вернуть ответ: ему нужно factorial(4), и он ждёт. Тот ждёт factorial(3), и так до factorial(0), который возвращает 1 без всяких вызовов. Тут стопка начинает разбираться: factorial(1) получает 1 и возвращает $1 \cdot 1$, factorial(2) получает 1 и возвращает 2, и так вверх до 120. Рекурсия работает в два хода: сначала спускается, откладывая умножения, потом поднимается, выполняя их.
if n == 0: return 1: проследите, чем тогда кончится спуск.Доверьтесь рекурсии
Проследить ход рекурсии по шагам полезно один-два раза. Писать рекурсию так нельзя: у Ханойской башни из восьми дисков 511 вызовов, и держать их в голове бессмысленно. Опытные программисты рассуждают иначе. Когда пишете шаг, считайте, что функция уже работает на задачах поменьше, и думайте только о том, как из их ответа собрать свой. Это называют прыжком веры, но никакой веры здесь нет — есть индукция: если базовый случай верен, а шаг правильно собирает ответ из правильных ответов поменьше, функция верна для всех $n$.
Попробуйте этот способ думать на трёх маленьких функциях. Сумма списка — первый элемент плюс сумма остальных. Строка — палиндром, если первая и последняя буквы совпадают, а середина — палиндром. Количество цифр числа — одна плюс количество цифр числа без последней цифры.
В каждой функции две строки мысли: что делать с самой маленькой задачей и как свести большую к меньшей. Про то, как именно total досчитает сумму остальных, думать не нужно — это её же работа на задаче поменьше. Проверьте себя.
Какая из функций при n = 5 никогда не дойдёт до базового случая?
С шагом минус два из пятёрки получаются 3, 1, −1, −3… — нечётные числа перепрыгивают через ноль, и базовый случай не наступает никогда. Шагу мало уменьшать задачу — он должен гарантированно привести её к базовому случаю. Исправить можно условием n <= 0.
Без дна
Что бывает, когда базовый случай не наступает, покажут ступеньки выше в режиме «без базового случая». А можно запустить вот это.
Обратный отсчёт проскочил ноль, ушёл в минус и на −991 остановился с ошибкой RecursionError: maximum recursion depth exceeded — «превышена наибольшая глубина рекурсии». Каждый кадр занимает память, а память стека не бесконечна. Если бы Python не следил за глубиной, бесконечная рекурсия обрушила бы всю программу, поэтому он разрешает около тысячи вложенных вызовов, а на следующем останавливает программу понятной ошибкой. Предел показывает функция sys.getrecursionlimit; в него входят и несколько кадров, занятых ещё до первого вызова. Такую аварию называют переполнением стека, по-английски stack overflow. Так же назван самый известный сайт вопросов и ответов для программистов.
Предел можно поднять функцией sys.setrecursionlimit, но это лечит симптом. Глубина нашей рекурсии равна $n$: факториал тысячи упрётся в предел, хотя считается мгновенно. Задачи, в которых рекурсия спускается на тысячи этажей, лучше решать циклом или делать рекурсию мельче — например, делить задачу не на «один и остальные», а пополам. На этом построена глава 21, и так же решается первая задача этой главы.
Мастерская: дерево из главы 0
В главе 0 черепаха нарисовала дерево из десятка строк, и мы пообещали объяснить, как она это сделала. Вот та же функция; теперь вы прочтёте в ней каждую строку.
Ветка — это ствол, на котором растут две ветки поменьше. Определение ссылается само на себя, как Ханойская башня, и код повторяет определение. Одна деталь держит всё дерево: функция возвращает черепаху туда, откуда её взяла, и в том же направлении. Поворот налево на 25°, направо на 50° и налево на 25° в сумме дают ноль, а t.back(length) отводит черепаху назад вдоль ствола. Благодаря этому, рисуя левое поддерево, можно не думать, где черепаха окажется потом: она будет там же, где была до вызова. Это то же доверие к рекурсии, только в геометрии. Уберите строку t.back(length), запустите ячейку снова и сравните деревья.
Посчитаем ветки. На глубине 9 одна ветка, на глубине 8 — две, на глубине 7 — четыре, и так до 256 на глубине 1: всего $1 + 2 + 4 + \dots + 256 = 2^9 - 1 = 511$. Снова $2^n - 1$, и не случайно: дерево вызовов branch устроено как дерево вызовов hanoi, только каждый вызов рисует ветку, а не перекладывает диск.
Запустите в мастерской «Как рисует рекурсия» для дерева. Можно было ждать, что черепаха пойдёт ярусами: сначала все толстые ветки, потом тонкие. Она же уходит вглубь по самой левой ветке до самого кончика, возвращается на шаг, рисует соседний кончик и так обходит всё дерево. Это порядок обхода в глубину, и его диктует стек: пока вызов не закончился, его соседи справа ждут.
Снежинка Коха
В 1904 году шведский математик Хельге фон Кох описал кривую, которая состоит из одних изломов. Правило: возьмите отрезок, разделите на три части и среднюю замените двумя сторонами равностороннего треугольника — получится ломаная из четырёх отрезков. С каждым из них сделайте то же самое. И так без конца. Три такие кривые на сторонах треугольника дают снежинку.
Ни одного цикла внутри koch, только четыре вызова и три поворота. Каждый уровень заменяет отрезок четырьмя отрезками втрое короче, поэтому длина кривой умножается на $\frac43$. На глубине 4 у снежинки $3 \cdot 4^4 = 768$ отрезков, а периметр в $\left(\frac43\right)^4 \approx 3{,}2$ раза больше, чем у исходного треугольника. Если продолжать без конца, периметр уйдёт в бесконечность, а площадь останется конечной: снежинка не вылезет за круг, описанный вокруг треугольника. Такие фигуры, у которых новые подробности видны на любом увеличении, называют фракталами; в «Царице наук» есть глава о них — с ответом на вопрос, какой длины берег Британии.
Треугольник Серпинского
Ещё один фрактал: треугольник, составленный из трёх треугольников вдвое меньше, каждый из которых составлен из трёх ещё меньших. Его описал польский математик Вацлав Серпинский в 1915 году. Рекурсия здесь прямо читается из определения: нарисовать треугольник глубины $d$ — значит нарисовать три треугольника глубины $d - 1$ в его углах.
Число $0{,}866$ — это $\frac{\sqrt3}{2}$, высота равностороннего треугольника со стороной 1. На глубине 5 закрашено $3^5 = 243$ треугольника. Тот же узор проступит в треугольнике Паскаля, если закрасить в нём нечётные числа, а в последней задаче этой главы вы сложите его из строк со звёздочками.
Обратно к папкам
У нас есть всё, чтобы ответить на последнюю телеграмму прошлой главы. Размер папки — сумма по всему, что в ней лежит: файл даёт свой размер, а вложенная папка — свой размер, который считается той же функцией.
Базовый случай здесь не стоит отдельной строкой в начале функции: папка, в которой одни файлы, не делает рекурсивных вызовов, на ней спуск и заканчивается. Глубина рекурсии равна глубине вложенности папок, какой бы она ни была. Вложенные циклы прошлой главы сдались на третьем этаже, а эта функция одинаково спокойно спустится и на третий, и на тридцатый.
Тем же приёмом печатают оглавление папки — как это делает команда tree в терминале. Отступ растёт с глубиной, поэтому его передают параметром.
Так же обходят любые вложенные данные. JSON из прошлой главы — это словари и списки, вложенные друг в друга на любую глубину. Список, в котором бывают списки, — тоже. Функция, которая обходит такую структуру, почти всегда выглядит одинаково: перебрать элементы; если элемент простой — обработать, если сам структура — вызвать себя.
Все коды азбуки
Рекурсия умеет не только обходить готовое, но и перебирать все варианты. Вернёмся к азбуке Морзе. Сколько существует кодов из $n$ сигналов? Код из $n$ сигналов — это код из $n - 1$ сигнала, к которому дописали точку или тире. Значит, все коды длины $n$ получаются из всех кодов длины $n - 1$ — снова задача внутри задачи.
Кодов из $n$ сигналов $2^n$: каждый следующий сигнал удваивает число вариантов. Из одного, двух, трёх и четырёх сигналов можно составить $2 + 4 + 8 + 16 = 30$ кодов. А в русском алфавите азбуки 32 буквы. Вот почему двум буквам, «э» и «ъ», в таблице прошлой главы достались коды из пяти сигналов: коротких на всех не хватило. Почему именно им — вопрос к истории, а не к частотам: «ф» и «щ» встречаются в романе даже реже «э».
Самое тонкое место здесь — базовый случай. Кодов длины 0 не «ни одного»: есть один, пустая строка. Если вернуть пустой список, цикл на следующем уровне ничего не переберёт, и пустыми окажутся все ответы. В базовом случае ошибаются чаще всего, а проверяют его так же, как базу индукции: на самом маленьком входе ответ должен быть верным сам по себе.
Похоже строятся перестановки — все способы расставить буквы слова по порядку. Первой можно поставить любую букву, а за ней — любую перестановку остальных. У трёх разных букв $3 \cdot 2 \cdot 1 = 6$ перестановок, у $n$ разных — $n!$, факториал из раздела про стек. Написать их вам предстоит в задачах.
Рекурсия или цикл
Факториал можно посчитать и циклом — так даже проще.
Цикл не упирается в предел глубины и не тратит память на тысячи кадров. Для задач, которые сводятся к задаче «на единицу меньше» по прямой цепочке — факториал, сумма списка, обратный отсчёт, — цикл обычно лучше. Рекурсия выигрывает там, где задача ветвится: Ханойская башня, деревья, папки, перебор вариантов. Написать их циклом можно, но придётся самим хранить стопку недоделанных дел — то, что рекурсия получает от стека вызовов бесплатно.
Есть и третий случай: ветвящаяся рекурсия, которая повторяет одну и ту же работу. Числа Фибоначчи — 0, 1, 1, 2, 3, 5, 8, 13, … — каждое следующее равно сумме двух предыдущих, и определение просится в код. В «Царице наук» о них целый рассказ.
С каждыми пятью единицами $n$ время растёт больше чем вдесятеро. Причина видна на дереве вызовов.
fib(n): каждый кружок — вызов, под ним — вызовы, которые он сделал. Нажмите на кружок — подсветятся все вызовы с тем же аргументом. Переключатель «с памятью» показывает, что останется, если запоминать готовые ответы.В дереве fib(5) вызов fib(3) встречается дважды, а fib(2) — трижды, и каждый раз всё считается заново. Всего 15 вызовов ради числа 5. Для fib(30) вызовов 2 692 537, для fib(40) — 331 160 281, а различных аргументов среди них всего 41. С каждой единицей $n$ дерево становится примерно в 1,6 раза больше (это золотое сечение), а за пять единиц — в одиннадцать.
Это та же беда, что у Ханойской башни, только напрасная: брахманам все $2^{64} - 1$ ходов действительно нужны, а здесь почти вся работа — повторы. Как сосчитать время таких программ заранее, расскажет глава 13. Как запомнить уже посчитанное и обойтись сорока одним вычислением вместо сотен миллионов вызовов — глава 22.
Задачи
Пять задач. В каждой подумайте сначала о двух вещах: какой случай самый простой и как свести задачу к меньшей. Тесты вызывают ваши функции и сравнивают то, что они вернули.
Напишите функцию power(x, n), которая возвращает $x^n$ для целого $n \ge 0$. Пользоваться ** и pow нельзя. Рекурсия в лоб, $x^n = x \cdot x^{n-1}$, не годится: тесты дают $n$ до миллиона, и она упрётся в предел глубины, а цикл из миллиона умножений слишком долог. Тесты считают умножения: их должно быть не больше, чем примерно удвоенное число двоичных знаков $n$ — для миллиона это около сорока.
Если $n$ чётное, то $x^n = \left(x^{n/2}\right)^2$: одна рекурсивная задача вдвое меньше и одно умножение. Если нечётное, то $x^n = x \cdot x^{n-1}$, а $n - 1$ уже чётное.
Посчитайте half = power(x, n // 2) один раз и умножьте half * half. Если вызвать power(x, n // 2) * power(x, n // 2), вызовов снова станет порядка $n$, как у рекурсии в лоб.
Каждый вызов делит $n$ пополам, поэтому глубина рекурсии — число двоичных знаков $n$: для миллиона это 20. На каждом уровне одно-два умножения. Так возводят в степень везде, где числа огромные: в главе 60 этим же приёмом шифр RSA возводит числа из сотен цифр в такие же огромные степени. Подсказка про half не мелочь: два одинаковых вызова вместо одного превращают двадцать уровней в два миллиона вызовов — как у Фибоначчи, только с повторами по собственной вине.
Напишите функцию flatten(items), которая получает список, где элементы — числа или такие же списки на любой глубине, и возвращает плоский список всех чисел в том же порядке. Например, flatten([1, [2, [3, 4]], [], [[5]]]) — это [1, 2, 3, 4, 5]. Исходный список менять нельзя.
Заготовка раскрывает только один уровень вложенности: на [1, [2, [3]]] она вернёт [1, 2, [3]]. Внутренний список мало перебрать: его нужно расплющить той же функцией.
Для элемента-списка вызовите flatten(x) и добавьте все числа из результата в result — циклом или методом extend.
Тот же шаблон, что у folder_size: число добавляем сразу, список отдаём той же функции. Метод extend добавляет в список все элементы другого списка. Пустой вложенный список ничего не добавляет — отдельный случай для него не нужен.
Напишите функцию hanoi_moves(n, source, target, spare), которая не печатает ходы, а возвращает их списком кортежей (откуда, куда). Например, hanoi_moves(2, "A", "C", "B") — это [("A", "B"), ("A", "C"), ("B", "C")]. Ходов должно быть ровно $2^n - 1$, и все по правилам.
Возьмите функцию hanoi из главы. Базовый случай теперь возвращает пустой список ходов: return []. А рекурсивные вызовы возвращают списки, которые нужно сохранить в переменные.
Ходы для $n$ дисков — это ходы первой башни поменьше, потом один ход большого диска, потом ходы второй башни: first + [(source, target)] + second.
Функция, которая возвращает результат, удобнее функции, которая печатает: её ответ можно проверить, посчитать, отдать головоломке. Тесты, например, проигрывают ходы на трёх стопках и так убеждаются, что они законны. Склеивание списков на каждом уровне стоит времени, но для башен, которые вообще можно дождаться, этим можно пренебречь.
Напишите функцию permutations(s), которая возвращает список всех различных перестановок букв строки s, отсортированный по алфавиту. Например, permutations("кот") — это ["кот", "кто", "окт", "отк", "тко", "ток"]. Если буквы повторяются, одинаковые перестановки в ответ попадают один раз: permutations("аба") — это ["ааб", "аба", "баа"]. У пустой строки одна перестановка — пустая строка: [""]. Модулем itertools пользоваться нельзя.
Первой может стоять любая буква. Для каждой позиции i возьмите букву s[i] и приставьте её ко всем перестановкам остальных букв: s[:i] + s[i + 1:].
Базовый случай — строка длины 0 или 1: у неё одна перестановка, она сама. Повторы уберёт set из прошлой главы, а sorted расставит по алфавиту.
У восьми разных букв $8! = 40\,320$ перестановок — список растёт как факториал, быстрее любой степени. Соедините эту функцию с множеством слов «Войны и мира» из прошлой главы, и найдутся перестановки «ясно», которые есть в романе: «ясно», «нося» и «соня». Так ищут анаграммы, когда слово одно, а словарь большой; когда слов много, лучше ключ из отсортированных букв.
Напишите функцию sierpinski(n), которая возвращает треугольник Серпинского порядка $n$ списком строк. Порядок 0 — одна звёздочка: ["*"]. Треугольник порядка $n$ — это треугольник порядка $n - 1$, отодвинутый вправо, а под ним два таких же рядом через пробел. Все строки одной длины $2^{n+1} - 1$, пустые места — пробелы, в том числе в конце строки. Порядок 2:
Здесь строки — " * ", " * * ", " * * " и "* * * *", по семь символов. Нарисовать ответ можно и клетками: show_grid(sierpinski(4)) из модуля cs.viz.
Треугольник поменьше small уже есть. Ширина его строк — w = len(small[0]). Верхняя половина ответа — строки small, к которым с обеих сторон добавлено поровну пробелов, чтобы ширина стала 2 * w + 1.
С каждой стороны нужно (w + 1) // 2 пробелов. Нижняя половина — каждая строка small, повторённая дважды через пробел: row + " " + row.
Рисунок порядка $n$ собран из трёх рисунков порядка $n - 1$, как и черепаший треугольник выше, только вместо координат — пробелы. Строк $2^n$, звёздочек $3^n$: на каждом уровне их втрое больше. Проверьте на show_grid(sierpinski(5)).
Куда дальше
Вспомните функции, которые обходили папки и вложенные списки. folder_size складывает размеры, show печатает имена, nested_sum складывает числа, flatten собирает их в список. Скелет у всех один: перебрать элементы, простой — обработать, составной — отдать той же функции. Различается только начинка: что сделать с простым элементом. Написать скелет один раз, а начинку передавать отдельно пока не получается, ведь в функцию мы передавали только числа, строки и списки. А если передать в неё другую функцию? Python это разрешает, и из этого вырастает целый способ писать программы. О нём — глава 10.