Теоретический минимум по Computer Science

········fragrances ← fragrances + new_fragrances

····return fragrances

Добавление каждого нового цветка приводит к удвоению количества ароматов в множестве fragrances, что говорит об экспоненциальном росте (2^k+1 = 2 × 2^k). Алгоритмы, которые удваивают число операций, если объем входных данных увеличивается на один элемент, — экспоненциальные, их временная сложность — O(2ⁿ).

Генерирование степенных множеств эквивалентно генерированию таблиц истинности (см. раздел «Логика» в главе 1). Если обозначить каждый цветок логической переменной, то любой аромат легко представить в виде значений True/False этих переменных. В таблице истинности каждая строка будет возможной формулой аромата.

Рис. 3.2. Итеративное перечисление всех ароматов с использованием четырех цветков

3.2. Рекурсия

Мы говорим о рекурсии, когда функция делегирует работу своим клонам. Рекурсивный алгоритм естественным образом приходит на ум, когда нужно решить задачу, сформулированную с точки зрения самой себя. Например, возьмем известную последовательность Фибоначчи. Она начинается с двух единиц, и каждое последующее число является суммой двух предыдущих: 1, 1, 2, 3, 5, 8, 13, 21. Как создать функцию, возвращающую n-е число Фибоначчи (рис. 3.3)?

Рис. 3.3. Рекурсивное вычисление шестого числа Фибоначчи

function fib(n)

····if n ≤ 2

········return 1

····return fib(n — 1) + fib(n — 2)

При использовании рекурсии требуется творческий подход, чтобы понять, каким образом задача может быть поставлена с точки зрения самой себя. Чтобы проверить, является ли слово палиндромом[30], нужно посмотреть, изменится ли оно, если его перевернуть. Это можно сделать, проверив, одинаковы ли первая и последняя буквы слова и не является ли палиндромом заключенная между ними часть слова (рис. 3.4).

Рис. 3.4. Рекурсивная проверка, является ли слово racecar палиндромом

function palindrome(word)

····if word.length ≤ 1

········return True

····if word.first_char ≠ word.last_char

········return False

····w ← word.remove_first_and_last_chars

····return palindrome(w)

Рекурсивные алгоритмы имеют базовые случаи, когда объем входных данных слишком мал, чтобы его можно было продолжать сокращать. Базовые случаи для функции fib — числа 1 и 2; для функции palindrome это слова, состоящие из единственной буквы или не имеющие ни одной буквы.

Рекурсия против итераций

Рекурсивные алгоритмы обычно проще и короче итеративных. Сравните эту рекурсивную функцию с power_set из предыдущего раздела, которая не использует рекурсию:

function recursive_power_set(items)

····ps ← copy(items)

····for each e in items

·······ps ← ps.remove(e)

·······ps ← ps + recursive_power_set(ps)

·······ps ← ps.add(e)

····return ps

Эта простота имеет свою цену. Рекурсивные алгоритмы при выполнении порождают многочисленные копии самих себя, создавая дополнительные вычислительные издержки. Компьютер должен отслеживать незаконченные рекурсивные вызовы и их частичные вычисления, что требует большего объема памяти. При этом дополнительные такты центрального процессора расходуются на переключение с одного рекурсивного вызова на следующий и назад.

Эту проблему можно наглядно увидеть на деревьях рекурсивных вызовов — диаграммах, показывающих, каким образом алгоритм порождает новые вызовы, углубляясь в вычисления. Мы уже видели деревья рекурсивных вызовов для поиска чисел Фибоначчи (см. рис. 3.3) и для проверки слов-перевертышей (см. рис. 3.4).

Если требуется максимальная производительность, то можно избежать этих дополнительных издержек, переписав рекурсивный алгоритм в чисто итеративной форме. Такая возможность есть всегда. Это компромисс: итеративный программный код обычно выполняется быстрее, но вместе с тем он более громоздкий и его труднее понять.

3.3. Полный перебор

Полный перебор, он же метод «грубой силы», предполагает перебор всех случаев, которые могут быть решением задачи. Эта стратегия также называется исчерпывающим поиском. Она обычно прямолинейна и незамысловата: даже в том случае, когда вариантов миллиарды, она все равно опирается исключительно на силу, то есть на способность компьютера проверить их все.

Рис. 3.5. Простое объяснение: полный перебор[31]

Давайте посмотрим, как ее можно использовать, чтобы решить следующую задачу.