Примеры задач на рекурсию

Рита: Ребята, а давайте для закрепления материала порешаем задачи на рекурсию?
Тимофей: Отличная идея. Теория теорией, а разбор задач — полезная штука.
Алгоритм бинарного поиска — известный пример использования стратегии «разделяй и властвуй». Разберёмся, как алгоритм работает и напишем к нему код.
Задача: найти в массиве элемент и вернуть его индекс. Если элемент не найден, вернуть -1. Массив должен быть обязательно отсортирован. В нашем случае — по возрастанию. Предположим, что в массиве нет дубликатов.
В алгоритме бинарного поиска мы проверяем центральный элемент массива. Если центральный элемент:
  1. равен искомому, возвращаем его индекс;
  2. больше искомого, продолжим рекурсивный поиск в левой половине массива;
  3. меньше искомого, продолжим рекурсивный поиск в правой половине массива.
Массив отсортирован, поэтому мы ищем элемент только в левой или правой части массива.
Функция принимает 4 параметра:
  1. массив;
  2. искомый элемент;
  3. левую границу;
  4. правую границу.
Чтобы вычислить индекс середины массива, воспользуемся формулой:
Скопировать кодPYTHON
mid = l + (r - l) // 2
Применяем операцию целочисленного деления, так как вычисляемый индекс должен быть целым числом.
Проверяем, равен ли центральный элемент искомому. Если равен, возвращаем индекс.
Скопировать кодPYTHON
if arr[mid] == x:
    return mid
Если центральный элемент больше искомого, заменяем r на mid - 1 и рекурсивно повторяем процедуру. Вычитаем 1, ведь элемент на позиции mid уже проверен.
Скопировать кодPYTHON
elif arr[mid] > x: 
    return binarySearch(arr, x, l, mid - 1)
Если центральный элемент меньше искомого, заменяем l на mid + 1 и рекурсивно повторяем процедуру.
Скопировать кодPYTHON
else: 
    return binarySearch(arr, x, mid + 1, r)
На каждом шаге сужается диапазон поиска. Правая граница сдвигается влево, либо левая — вправо. В какой-то момент левая граница может стать больше правой. Тогда рекурсивные вызовы нужно остановить. Можно сделать вывод, что искомого элемента в массиве нет и вернуть -1.
Напишем код алгоритма целиком:
Скопировать кодPYTHON
def binarySearch(arr, x, l=0, r=len(arr)-1): 
    if r >= l: 
        mid = l + (r - l) // 2

        if arr[mid] == x: 
            return mid 

        elif arr[mid] > x: 
            return binarySearch(arr, x, l, mid - 1) 

        else: 
            return binarySearch(arr, x, mid + 1, r) 
    else: 
        return -1
Алгоритм можно легко модифицировать для поиска в массиве, отсортированном по убыванию. В этом случае, если центральный элемент меньше искомого, нужно продолжать поиск в левой части. А если больше — в правой.
Скопировать кодPYTHON
def binarySearch(arr, x, l=0, r=len(arr)-1): 
    if r >= l: 
        mid = l + (r - l) // 2

        if arr[mid] == x: 
            return mid 

        elif arr[mid] < x: 
            return binarySearch(arr, x, l, mid - 1) 

        else: 
            return binarySearch(arr, x, mid + 1, r) 
    else: 
        return -1
Теперь рассмотрим алгоритм быстрого возведения в степень.
Допустим, нужно возвести 2 в степень 4. Перемножим 2 четыре раза. Получим 16.
Теперь предположим, что нужно возвести 2 в степень 100. Придётся перемножить 2 сто раз.
Но можно оптимизировать алгоритм и возвести 2 в степень 4 быстрее.
Умножим 2 на 2. Получим 4. Затем умножим 4 на 4. Получим 16. Мы использовали три операции умножения вместо четырёх.
Допустим, нужно возвести 2 в степень 8. Для этого нужно 2 в степени 4 умножить на себя.
По сравнению с предыдущим примером добавится всего одна операция умножения.
Но мы рассмотрели только пример возведения числа в чётную степень. А что делать, если степень нечётная?
Например, нужно возвести 3 в степень 5.
Тогда возведём 3 в степень 4 по аналогии с предыдущим примером . Затем умножим результат на 3.
То есть: 1. Если степень чётная, разделим значение на 2. Результат умножим сам на себя. 2. Если степень нечётная, вычтем из значения 1 и получим чётную степень. Посчитаем результат для чётной степени и умножим его на само число.
Описанный алгоритм удобно реализовать в виде рекурсивной функции:
Скопировать кодPYTHON
def recursive_power(x, n):
    if n == 0:
        return 1

    if n % 2:
        return x * recursive_power(x, n - 1)
    else:
        m = recursive_power(x, n // 2)
        return m * m
Часто рекурсию применяют для генерации объектов. Например, числовых или скобочных последовательностей.
Рассмотрим пример генерации всех двоичных последовательностей длины n.
Функция принимает в качестве параметра число n и строку prefix. Вызываем функцию с параметром n и значением prefix, равным пустой строке. Далее будем добавлять в эту строку 0 и 1. В каждом рекурсивном вызове n означает, сколько ещё символов нужно добавить в строку. Когда длина станет равной n, напечатаем результат. Это и будет базовый случай рекурсии в этой задаче.
В рекурсивной случае функция вызывает себя дважды, но с разными параметрами. В первый раз она добавляет в строке prefix 0, а во второй раз — 1. При этом значение n уменьшается на 1, ведь мы добавляем один символ. Значит, после каждой операции остаётся добавить на один символ меньше.
Рекурсивная функция, которая решает эту задачу:
Скопировать кодPYTHON
def gen_binary(n, prefix):
    if n == 0:
        print(prefix)
    else:
        gen_binary(n - 1, prefix + '0')
        gen_binary(n - 1, prefix + '1')
Решение этой задачи удобно представлять в виде бинарного дерева. Начинаем с пустой строки. Если идём влево, добавляем 0, если вправо — 1.
Если пройти от корня по всем веткам, получим все возможные последовательности из 0 и 1 длины 3.
Скопировать кодPYTHON
                            ''
                          /     \
                         0       1
                        / \     /  \
                       0   1   0    1
                      / \ / \ / \  / \
                     0   10  10  10   1
Кстати, всего таких последовательностей 2 в степени n.
Разберёмся почему. Всего n позиций. На каждой из них может стоять 0 или 1. То есть 2 варианта. По теореме умножения получим 2 * 2 * 2 * ... * 2 n раз. Вы уже решали похожие задачи в предыдущих уроках на курсе.
Если посчитаете количество веток дерева, убедитесь, что их действительно 2 в степени 3, то есть 8.