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

    Следующая задача - сравнение двух строк (конечно, в языке Python мы можем просто воспользоваться операцией ==). Логическая функция, решающая эту задачу, будет иметь два строковых входных параметра. Если их длины различны, алгоритм немедленно вернёт False уже в начальном условии. Таким образом, сравнивать строки имеет смысл при одинаковой их длине, которая и является размером задачи.

Линейно-рекурсивный алгоритм

    Наименьший экземпляр задачи - когда обе строки пусты и результат, очевидно, равен True. На этом шаге мы предположим, что никаких дополнительных начальных условий, приводящих к линейно-рекурсивной функции, нет. Применим декомпозицию с уменьшением размера задачи на 1. Она сводится к поштучному отбрасыванию совпавших символов (в одной и той же позиции) в обеих входных строках. Отбрасывание первых символов приводит к следующей рекурсивной схеме, где s и t - две входные строки длиной n:

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

              False,                           если length(s) ≠ length(t),
    f(s, t) = True,                            если n = 0,
              (s0 = t0) ∧ f(s1...n-1, f1..n-1), если n > 0       . 

    В примере 5.3 приводится соответствующий код линейно-рекурсивной функции.

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

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

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