На этом шаге мы рассмотрим, когда может пригодиться анализ конкретных экземпляров задачи.
В примере предыдущего шага, где выполняется сложение первых n положительных целых чисел, результат рекурсивного метода легко выразить в виде общей функции от входного параметра n. Иными словами, выражения из правой части общей схемы здесь получаются легко. Однако в других задачах описать результаты рекурсивных методов (скажем, некоторой формулой) гораздо сложнее, и потому труднее понять, как вывести решение задачи из результатов её подзадач. В таких случаях на первых порах полезен подход, заключающийся в анализе конкретных экземпляров задачи.
Рассмотрим задачу сложения цифр некоторого неотрицательного целого числа n и допустим, что выбрана декомпозиция, уменьшающая количество цифр на 1 за счёт отбрасывания наименьшей значащей цифры исходного числа. Эта информация представлена в левых блоках общей схемы. Однако определение выхода, как и функции от n, в правых блоках схемы может оказаться сложным. Например, его можно описать следующей суммой:
⌊ log10n ⌋
∑ (n // 10i) % 10 (2.2)
i=1
Несмотря на то что мы могли бы использовать эту формулу для вывода рекурсивных условий, мы продолжим анализировать конкретные экземпляры задачи. Например (ради простоты можно отказаться от использования имени метода в колонке результатов и от маркировки стрелок):
Из этих схем нетрудно видеть, что результат метода - это сумма последней (подчеркнутой) цифры исходного числа и результата подзадачи.
На следующем шаге мы рассмотрим альтернативные обозначения.
