На этом шаге мы рассмотрим особенности реализации такого алгоритма.

На примере 78 шага можно учесть "короткое замыкание", добавив дополнительное начальное условие. В частности, алгоритм может сразу вернуть False при обнаружении первого несовпадения символов в одной и той же позиции строк. Таким образом, можно добавить начальное условие с проверкой s₀ ≠ t₀. В этом случае алгоритм мог бы сразу вернуть False. Такое начальное условие гарантирует, что в рекурсивном условии s₀ = t₀. Таким образом, новая рекурсивная схема будет такой:

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

Пример 5.4. Функция с хвостовой рекурсией, сопоставляющая две строки

1
2
3
4
5
6
7
8
9

def equal_strings_tail(s, t):
    if len(s) != len(t):
        return False
    elif s == '':
        return True
    elif s[0] != t[0]:
        return False
    else:
        return equal_strings_tail(s[1:], t[1:])

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

Со следующего шага мы обратимся к алгоритмам поиска в списке.

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