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

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

Обращение строки

    Рассмотрим задачу обращения строки. В частности, создадим функцию f(), которая получает на входе строку и возвращает её обращение - цепочку из тех же символов, следующих в обратном порядке. Например, f('abcd') = 'dcba'.

    Размер задачи - это длина входной строки. Начальное условие выполняется при пустой входной строке, когда результатом, очевидно, является тоже пустая строка. Для уменьшения размера задачи в рекурсивном условии следует исключать по одному символу входной строки. Явные кандидаты для этого - первый или последний символ строки. Исключение первого символа приводит к следующей схеме, где входная строка s записывается в виде последовательности символов s₀ s₁ ... s_n-2 s_n-1:

    Таким образом, функция должна просто добавить первый символ в конец результата подзадачи, связанной с s₁ ... s_n-2s_n-1 (символ "+" обозначает конкатенацию строк). Эта рекурсивная функция вместе с начальным условием реализована в примере 4.11.

def reverse_string(s):
    if s == '':
        return ''
    else:
        return reverse_string(s[1:]) + s[0]    

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

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