На этом шаге мы приведем требования, накладываемые на начальные условия.

    Начальные условия - это такие экземпляры задачи, для решения которых не нужна рекурсия, точнее не нужны рекурсивные вызовы. В самом общем случае начальное условие - это наименьший экземпляр задачи, результат которой определяется тривиально, а иногда даже не требует вычислений. Например, значение первого и второго чисел Фибоначчи - это просто 1, что прямо следует из их определения. Очевидно, что "сумма" первого положительного целого числа есть 1. Аналогично, "сумма" цифр неотрицательного целого числа n из одной цифры (когда n < 10), очевидно, равна самой этой цифре (n). Заметьте, что эти функции в начальных условиях просто возвращают значение, не выполняя ни сложения, ни других математических действий.

    Некоторые методы могут требовать нескольких начальных условий. Например, в формуле (1.2) для чисел Фибоначчи задано два начальных условия - одно для n = 1 и другое для n = 2. Так как оба начальных условия имеют одно и то же значение (1), функция в примере 1.3 может использовать одно логическое выражение ((n == 1) or (n == 2)), объединяющее оба условия. Другие методы должны использовать каскадный оператор if, чтобы проверить каждое начальное условие. Например, функция (1.6) определяет одно начальное условие для n = 1 и другое для n = 2, так как они возвращают разные значения для каждого из входов. По этой причине соответствующий код в примере 1.2 тоже разделяет эти два условия.

    Одно из достоинств рекурсивного программирования - лаконичность кода, что способствует его пониманию. В связи с этим рассмотрим функцию вычисления факториала (1.3). Если начальные условия представляют собой тривиальные (наименьшие) экземпляры задачи, можно было бы потребовать, чтобы определение функции включало также случай 1! = 1. Но значение 1! можно получить и из рекурсивного условия, так как 1! = 0! * 1 = 1 * 1 = 1. Следовательно, хотя 1! = 1 - очевидно, верное начальное условие, его включение в формулу было бы избыточным и потому необязательно. Кроме того, такие необязательные условия могут вводить в заблуждение, поскольку программисты, пытающиеся понять рекурсивный код, могут посчитать их необходимыми для получения правильного результата функции. Таким образом, ради краткости и ясности обычно рекомендуется включать наименьшее количество начальных условий, приводящих к правильным рекурсивным определениям. Наконец, избыточные начальные условия обычно не оказывают существенного влияния на эффективность рекурсивной программы. В общем, если они и могут сократить количество вызовов рекурсивной функции для некоторых входных значений, то сэкономленное время вычисления зачастую незначительно. Например, если 1! включён в начальные условия в функцию вычисления факториала, то рекурсивный процесс выполнит лишь на один рекурсивный вызов меньше, что едва ли повлияет на время его выполнения. Кроме того, коду потребовались бы две проверки условия, и он мог бы стать даже менее эффективным, чем тот, где оба условия вычислялись бы до перехода к рекурсивному условию.

    На примере функции вычисления факториала пример 2.1 иллюстрирует эту и другие основные ловушки, касающиеся начальных условий. Во-первых, метод вычисления факториала обеспечивает безупречную реализацию математической функции. Метод factorial_redundant() правилен, так как даёт правильный результат для любого неотрицательного целочисленного входного параметра. Однако он содержит дополнительное начальное условие - совершенно ненужное.

    Кроме того, мы должны также добиваться общности - крайне желательного свойства программ. Общие функции - это такие функции, которые работают правильно в широком диапазоне входных параметров и потому более применимы и полезны. Функция вычисления факториала (1.3) имеет своим входным параметром неотрицательное целое число и определяется так, чтобы быть применимой не только к каждому положительному целому числу, но также и к нулю. Замена начального условия 0! = 1 на 1! = 1 привела бы к менее общей функции, так как она не была бы определена для n = 0. Метод factorial_missing_base_case() реализует такую функцию. Если бы она была вызвана с входным параметром n = 0, она не дала бы правильного результата, погрузившись в бездну бесконечной рекурсии. А именно factorial_missing_base_ case(0) вызвала бы factorial_missing_base_case(-1), которая, в свою очередь, вызовет factorial_missing_base_case(-2) и т. д. На практике такой процесс (после выполнения большого количества вызовов функции) обычно останавливается с сообщением об ошибке времени выполнения программы (вроде "Переполнение стека" или "Превышена предельная глубина рекурсии"). Наконец, метод factorial_no_base_ case() всегда приводит к бесконечной рекурсии, так как не имеет начального условия и потому никогда не остановится.

def factorial(n):
    if n == 0:
        return 1
    else:
        return factorial(n - 1) * n


def factorial_redundant(n):
    if n == 0 or n == 1:
        return 1
    else:
        return factorial_redundant(n - 1) * n


def factorial_missing_base_case(n):
    if n == 1:
        return 1
    else:
        return factorial_missing_base_case(n - 1) * n  


def factorial_no_base_case(n):
    return factorial_no_base_case(n - 1) * n

    Для многих задач существуют такие экземпляры, результат которых можно получить без использования рекурсии, даже если их размер достаточно велик. Рассмотрим, например, задачу поиска некоторого элемента в списке. Размер задачи определяется множеством элементов списка. Первое начальное условие отвечает пустому списку (наименьшему экземпляру задачи нулевого размера), когда результат - очевидно, False. Кроме того, алгоритм может определять положение (скажем, в начале, в середине или в конце) найденного элемента списка и немедленно выдавать значение True, даже если список огромен (такие задачи мы рассмотрим позднее). В обоих случаях нет никакой необходимости в дальнейшем выполнении рекурсивных вызовов.

    На следующем шаге мы рассмотрим декомпозицию задачи.

Предыдущий шаг Содержание Следующий шаг