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

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

    Пусть f(n) проверяет чётность n, а g(n) - нечётность n. Если считать размером задачи n, то начальное условие для f(n) выполняется при n = 0 с очевидным результатом True. Напротив, g(0) = False. Для вывода рекурсивных условий можно уменьшать размер задачи на 1. Поскольку мы намерены вывести и f(n), и g(n), на основании индукции можно предположить, что они применимы к n - 1. Крайне важно, что для вывода f(n) нужно использовать g(n - 1), а для вывода g(n) - f(n - 1). С этой целью можно воспользоваться, например, такими простейшими свойствами: f(n) = g(n - 1) и g(n) = f(n - 1). Тогда два взаимно-рекурсивных метода можно закодировать, как в примере 9.1.

def is_even(n):
    if n == 0:
        return True
    else:
        return is_odd(n - 1)


def is_odd(n):
    if n == 0:
        return False
    else:
        return is_even(n - 1)    

    На следующем шаге мы рассмотрим игры со многими игроками.

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