Результат: ученик строит рекурсивное определение с достижимым базовым случаем, прослеживает кадры стека и оценивает число вызовов, глубину и дополнительную память в сравнении с итерацией.

Содержание:

  1. Распознать рекурсивную структуру

    • задача через меньший экземпляр той же задачи;
    • прямой и косвенный рекурсивный вызов;
    • параметр, описывающий размер оставшейся работы;
    • отделение рекурсивного определения от обычного повторного вызова.

  2. Задать базовый случай

    • вход, решаемый без нового вызова;
    • полнота базовых случаев;
    • результат на минимальном входе;
    • недопустимость базы, которая не охватывает достижимый конец разложения.

  3. Задать рекурсивный переход

    • вызов для строго меньшего состояния;
    • комбинирование локального результата с результатом подзадачи;
    • порядок вычисления аргументов;
    • возврат результата в предыдущий кадр.

  4. Доказать завершимость

    • уменьшающаяся мера;
    • нижняя граница меры;
    • достижимость базового случая;
    • предусловия для отрицательных, нулевых и граничных входов;
    • пример перехода, который не уменьшает задачу и приводит к бесконечной рекурсии.

  5. Проследить стек вызовов

    • отдельный кадр каждого незавершённого вызова;
    • параметры и локальные переменные кадра;
    • точка возврата;
    • фаза углубления;
    • фаза разворачивания;
    • порядок побочных действий до и после рекурсивного вызова.

  6. Оценивать число вызовов и глубину

    • линейная глубина;
    • логарифмическая глубина;
    • разветвлённая рекурсия;
    • повторное вычисление одинаковых подзадач;
    • экспоненциальный рост числа вызовов;
    • дополнительная память стека.

  7. Понимать риск переполнения стека

    • ограниченность доступной глубины;
    • StackOverflowException как особый аварийный исход;
    • невозможность считать математическую завершимость достаточной для любого размера;
    • отказ от эксперимента с опасной глубиной в основном проекте.

  8. Сравнивать рекурсию и цикл

    • одинаковый контракт и контрольные входы;
    • простота доказательства;
    • число операций;
    • дополнительная память;
    • возможность заменить линейную рекурсию итерацией;
    • отсутствие гарантии автоматической оптимизации хвостового вызова.