На этом шаге мы рассмотрим реализацию этой функции.

Один из самых популярных примеров вложенной рекурсии - функция Аккермана, определяемая следующим образом:

              n + 1,                 если m = 0
    A(n, m) = A(m - 1, 1),           если m > 0 и n = 1               (11.1)
              A(m - 1, A(m, n - 1)), если m > 0 и n > 1

где второй аргумент в последнем рекурсивном условии - рекурсивный вызов. Функция растёт чрезвычайно быстро даже при малых значениях аргументов и используется для проверки способности компиляторов оптимизировать рекурсию. В примере 11.7 приводится код функции, который совсем нетрудно реализовать.

Пример 11.7. Функция Аккермана

1
2
3
4
5
6
7

def ack(m, n):
    if m == 0:
        return n + 1
    elif n == 0:
        return ack(m - 1, 1)
    else:
        return ack(m - 1, ack(m, n - 1))

Архив с файлом можно взять здесь.

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

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