Лекция №5. Рекурсия и рекуррентные соотношения

Хорошевич Павел Александрович

Рекурсивные алгоритмы

Очередь

Алгоритм

номер в очереди():
    если я первый в очереди, то:
        обернуться и сказать "1"
    иначе:
        спросить у человека впереди номер в очереди()
        дождаться ответа
        обернуться и сказать результат сложения 1 + ответ

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

Рекурсия - это способ решения задач с помощью разбиения их на всё меньшие и меньшие подзадачи до тех пор, пока результат не сможет быть найден тривиальным способом.

  • Рекурсивный алгоритм должен вызывать сам себя.
  • Рекурсивный алгоритм должен иметь базовый случай - комбинацию значений аргументов, при которой алгоритм перестаёт вызывать сам себя.
  • Рекурсивный алгоритм должен изменять своё состояние и двигаться по направлению к базовому случаю.

Пример задачи

Пин-код от телефона состоит из четырёх цифр. Вы помните цифры кода и то, что они все разные, но забыли в каком порядке они расположены. Сколько, в худшем случае, комбинаций этих цифр вам нужно перебрать, чтобы разблокировать телефон?

Поиск ответа сводится к вычислению факториала: \(4!\)

\[ n! = n \cdot (n-1)! \]

Блок-схема решения

fact(n)

Реализация на Python

def fact(n):
    if n <= 1:
        return 1
    else:
        num = n * fact(n-1)
        return num
    
pin_vars = fact(4)
print(pin_vars)

Стек вызова функций

Из десятичной в двоичную

Используем рекурсию для перевода числа из десятичной системы счисления в двоичную.

def to_bin(x):
    if x > 0:
        to_bin(x // 2)
        print(x % 2, end="")

to_bin(13)

Числа Фибоначчи - рекурсивный алгоритм

Используем рекурсивный алгоритм для вычисления \(n\)-го числа последовательности.

\(F(0)=0\), \(F(1) = 1\).

\[F(n)=F(n-1) + F(n-2)\]

def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

Дерево вызова рекурсивной функции

Множественное ветвление

Рекурсивный алгоритм может содержать несколько базовых и рекурсивных случаев.

если базовый случай 1, то:
    вернуть решение 1
если базовый случай 2, то:
    вернуть решение 2
. . .
если рекурсивный случай 1, то:
    инструкции до рекурсии
    рекурсивный вызов алгоритма
    инструкции после рекурсии
если рекурсивный случай 2, то:
    инструкции до рекурсии
    рекурсивный вызов алгоритма
    инструкции после рекурсии
. . .

Простое или составное

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

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

def is_prime(x, d):
    if d == 1:
        return True
    elif x % d == 0:
        return False
    else:
        return is_prime(x, d - 1)

is_prime(42, 41)
is_prime(13, 12)

Рекурсия и графика

from turtle import *

def spiral(length, angle):
    if length > 10:
        forward(length)
        right(angle)
        spiral(length - 10, angle)
        
spiral(200, 90)

Динамическое программирование

Задача и подзадача

Динамическое программирование - метод решения задач оптимизации и подсчёта.

Суть метода - сохранение промежуточных вычислений для их повторного использования. Промежуточные решения являются решением подзадач.

Подзадача - это задача с меньшим количеством параметров или меньшими значениями параметров.

Решения подзадач сохраняются в одномерных или двухмерных таблицах - массивах или матрицах.

Одномерная таблица

Вычислите \(n\)-ое число Фибоначчи. \[ F(0)=0; F(1)=1; F(n)=F(n-1)+F(n-2) \]

fib_table
n = int(input("Введите n: "))
F = [0] * (n + 2)

F[0] = 0
F[1] = 1

for i in range(n):
    F[i + 1] += F[i]
    F[i + 2] += F[i]
    
print(F[n])

Двухмерная таблица

Робот движется по клеткам поля размером M x N. Он начинает своё движение в верхнем левом углу и движется в нижний правый угол поля. Робот может двигаться только вниз или вправо.

Сколькими различными способами робот может попасть в целевую клетку.

\[ grid(2, 3)=? \]

\[ grid(2, 3)=3 \]

\[ grid(1, 1)=1 \]

\[ grid(0, 2) = 0 \]

Решение крупной задачи сводится к подзадачам с меньшими значениями аргументов.

Элемент матрицы с индексом [M, N] будет хранить решение задачи для поля размером M x N.

grid
m = int(input("Количество строк M:"))
n = int(input("Количество столбцов N:"))

P = []
for i in range(m + 2):
    row = [0] * (n + 2)
    P.append(row)

P[1][1] = 1

for i in range(1, m + 1):
    for j in range(1, n + 1):
        P[i + 1][j] += P[i][j]
        P[i][j + 1] += P[i][j]
        
print(P[m][n])

Общий алгоритм использования ДП

  1. Определить набор параметров, которые уникальным образом описывают разные состояния задачи.

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

  3. Тип элементов таблицы зависит от ожидаемого результата.

Общий алгоритм использования ДП

  1. Инициализировать значения таблицы начальными значениями - решениями тривиальных подзадач.

  2. Перебрать элементы таблицы и заполнить следующие элементы таблицы с помощью значения текущего элемента. Продолжать, пока вся таблица не будет заполнена.

Зачастую ответ будет храниться в элементе таблицы заполненном последним.

Динамическое программирование - компромисс между временем выполнения алгоритма и объёмом используемой памяти.

Пример использования алгоритма

Дан массив целых неотрицательных чисел. Определить, можно ли получить число \(sum\) путём сложения чисел в массиве. Каждое число в массиве можно использовать неограниченное количество раз. \[ canSum(7, [5, 3, 4])=True \]

\[ canSum(8, [5, 7])=False \]

В качестве решённой подзадачи используем вариант, когда \(sum=0\):

\[ canSum(0, [1, 2, 3]) = True \]

\[ canSum(5, [2, 3, 4])=? \]

Решение снизу-вверх и сверху-вниз

  • Рекурсивное решение - подход сверху вниз. От общей задачи движемся к тривиальным решениям подзадач и возвращаемся к решению крупной задачи.
  • Итерационное решение - подход снизу-вверх. Используем решения тривиальных подзадач, чтобы получить решения более сложных подзадач и приходим к решению исходной задачи.

Решение снизу-вверх и сверху-вниз

Рекурсия и динамическое программирование

Рекурсивное вычисление чисел Фибоначчи:

def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n - 1) + fib(n - 2)
        
print(fib(500))

Мемоизация

Мемоизация - техника запоминания промежуточных результатов рекурсивных вызовов функции.

fib

fib
memo = [0] * 1000

def fib(n):
    if n <= 2:
        memo[n] = 1
        return 1
    else:
        if memo[n] == 0:
            memo[n] = fib(n - 1) + fib(n - 2)
        return memo[n]

print(fib(500))

Duck