Перейти к содержимому
Topos Uranos
Русский

Функции: итоги и задачи повышенной трудности

Краткое содержание

Этот урок завершает пятый раздел курса, посвящённый функциям. Он восстанавливает цепочку понятий, ведущую от объявления функции к рекурсии через стек вызовов, контракт, передачу параметров, область видимости и время жизни переменных и проектирование пошаговой детализацией; отделяет то, что из этого верно для любого языка, от того, что свойственно C++; собирает неопределённое поведение раздела вместе с тем, о чём предупреждает компилятор, что останавливает санитайзер и о чём не сообщает никто; повторяет в итоговой проверке навыки входной; и заканчивается шестью задачами повышенной трудности, которые объединяют весь раздел.

Цели обучения

  1. Разбивать задачу на функции, каждую со своим интерфейсом и своим контрактом (предусловием и постусловием), и тестировать их по отдельности.
  2. Выбирать способ передачи каждого параметра и способ возврата результатов и обосновывать этот выбор.
  3. Решать задачу рекурсией и доказывать её корректность по индукции, а её завершение с помощью убывающей меры, оценивая её стоимость числом вызовов.
  4. Распознавать неопределённое поведение раздела (путь без return, висячую ссылку, переполняющийся результат, исчерпанный стек) и переписывать программу без него.
  5. Отделять в изученном в разделе то, что верно для любого языка, от того, что свойственно C++.

Чего достиг раздел

Раздел ставил целью научить разбивать задачу на части с именами, каждую с интерфейсом и контрактом, и решать задачи рекурсией. Цель достигнута с опорой только на то, что введение объявило известным: циклы раздела 4 с их инвариантом и вариантом, спецификацию урока 1.1 и модель памяти раздела 2. Программа о дружественных числах, в которой скопированный цикл суммировал делители не того числа, теперь пишется с одной-единственной функцией, один раз проверенной на соответствие своему контракту.

Функции

Урок Функции научил объявлять, определять и вызывать функцию и разделил три момента: при компиляции каждый вызов сверяется с объявлением, встреченным раньше; при компоновке ищется определение; при выполнении вычисляются аргументы, в стеке вызовов создаётся кадр и управление переходит в тело. Он показал, что дойти до конца функции, которая не является void, без return означает неопределённое поведение, и завершился контрактом, предусловием и постусловием, который распределяет ответственность между вызывающим и функцией.

Параметры и область видимости

Урок Параметры и область видимости изучил, какими путями входят данные и выходят результаты: параметр по значению является копией; параметр по ссылке, вторым именем для ячейки вызывающего; константная ссылка читает без копирования. Отсюда следует правило выбора (значение для малого, константная ссылка для большого, которое только читается, ссылка лишь тогда, когда изменение и есть цель) и, для нескольких результатов, std::pair и std::tuple со структурными привязками. Он различил область видимости имени, свойство текста, и время жизни переменной, свойство выполнения, и закончился ссылкой, которая переживает свою ячейку.

Проектирование с помощью функций

Урок Проектирование с помощью функций научил решать, какие функции писать, методом пошаговой детализации: короткая main, которая вызывает лишь объявленные функции, и спуск к каждой из них, так что декомпозиция рисуется в виде дерева. Он установил критерии хорошего интерфейса и правило «одна функция, одна задача» с его признаками (союз в имени, функция, которая не помещается на экран, флаг) и со скрытыми эффектами, такими как глобальная переменная; представил перегрузку с её порядком предпочтения и неоднозначным вызовом; и переписал алгоритмы раздела 4 как функции, протестированные по отдельности.

Рекурсия

Урок Рекурсия научил тому, что функция может вызывать саму себя, чтобы решить меньший экземпляр задачи. Он доказал корректность по индукции, предполагая корректным меньший вызов, и завершение с помощью убывающей натуральной меры; проследил по стеку кадры, которые накапливаются и снимаются, и показал, как стек исчерпывается; предупредил, что тип результата переполняется намного раньше стека; и сравнил рекурсивное и итеративное вычисление чисел Фибоначчи: 2 692 5372\,692\,537 вызовов против 29 сложений для F30F_{30}.