Понимание рекурсии

Структуры данных и алгоритмы на Python

Miriam Antona

Software engineer

Определение

  • Функция вызывает саму себя
  • Применима почти везде, где используются циклы
    • заменяет циклы с помощью рекурсии
  • Позволяет решать задачи, которые на первый взгляд кажутся сложными
Структуры данных и алгоритмы на Python

Пример — факториал

$n!$

Структуры данных и алгоритмы на Python

Пример — факториал

$n!=n$ · $(n-1)$ · $(n-2)$ · $...$ · $1$

$5!=$ $5$ · $4$ · $3$ · $2$ · $1=120$

def factorial(n):
  result = 1
  while n > 1:
    result = n * result
    n -= 1
  return result

factorial(5)

120
Структуры данных и алгоритмы на Python

Пример — факториал с помощью рекурсии

$n!= n$ · $(n-1)!$

def factorial_recursion(n):
  return n * factorial_recursion(n-1)
  • Выполняется бесконечно!
Структуры данных и алгоритмы на Python

Пример — определение базового случая

  • Добавьте условие
    • предотвращает бесконечное выполнение алгоритма
  • Базовый случай факториала -> $n=1$
def factorial_recursion(n):
  if n == 1:

    return 1

  else:

    return n * factorial_recursion(n-1)

print(factorial_recursion(5))

120
Структуры данных и алгоритмы на Python

Как работает рекурсия

  • Компьютер использует стек для отслеживания функций
    • Стек вызовов
Структуры данных и алгоритмы на Python

Как работает рекурсия

  • factorial(5) запускается
  • Пока factorial(5) не завершилась -> запускается factorial(4)
  • Пока factorial(4) не завершилась -> запускается factorial(3)

Очередь с одним элементом, представляющим функцию.

Структуры данных и алгоритмы на Python

Как работает рекурсия

  • factorial(5) запускается
  • Пока factorial(5) не завершилась -> запускается factorial(4)
  • Пока factorial(4) не завершилась -> запускается factorial(3)
  • Пока factorial(3) не завершилась -> запускается factorial(2)

Очередь с двумя элементами, представляющими две функции.

Структуры данных и алгоритмы на Python

Как работает рекурсия

  • factorial(5) запускается
  • Пока factorial(5) не завершилась -> запускается factorial(4)
  • Пока factorial(4) не завершилась -> запускается factorial(3)
  • Пока factorial(3) не завершилась -> запускается factorial(2)
  • Пока factorial(2) не завершилась -> запускается factorial(1)

Очередь с тремя элементами, представляющими три функции.

Структуры данных и алгоритмы на Python

Как работает рекурсия

  • factorial(5) запускается
  • Пока factorial(5) не завершилась -> запускается factorial(4)
  • Пока factorial(4) не завершилась -> запускается factorial(3)
  • Пока factorial(3) не завершилась -> запускается factorial(2)
  • Пока factorial(2) не завершилась -> запускается factorial(1)

Очередь с четырьмя элементами, представляющими четыре функции.

Структуры данных и алгоритмы на Python

Как работает рекурсия

  • factorial(1) завершается
    • возвращает 1
  • factorial(2) завершается

Очередь с четырьмя элементами, представляющими четыре функции.

Структуры данных и алгоритмы на Python

Как работает рекурсия

  • factorial(1) завершается
    • возвращает 1
  • factorial(2) завершается
    • возвращает 2

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

Структуры данных и алгоритмы на Python

Как работает рекурсия

  • factorial(1) завершается
    • возвращает 1
  • factorial(2) завершается
    • возвращает 2
  • factorial(3) завершается
    • возвращает 6

Очередь с тремя элементами, представляющими три функции.

Структуры данных и алгоритмы на Python

Как работает рекурсия

  • factorial(1) завершается
    • возвращает 1
  • factorial(2) завершается
    • возвращает 2
  • factorial(3) завершается
    • возвращает 6
  • factorial(4) завершается
    • возвращает 24

Очередь с двумя элементами, представляющими две функции.

Структуры данных и алгоритмы на Python

Как работает рекурсия

  • factorial(1) завершается
    • возвращает 1
  • factorial(2) завершается
    • возвращает 2
  • factorial(3) завершается
    • возвращает 6
  • factorial(4) завершается
    • возвращает 24
  • factorial(5) завершается
    • возвращает 120

Очередь с одним элементом, представляющим одну функцию.

Структуры данных и алгоритмы на Python

Как работает рекурсия

  • factorial(1) завершается
    • возвращает 1
  • factorial(2) завершается
    • возвращает 2
  • factorial(3) завершается
    • возвращает 6
  • factorial(4) завершается
    • возвращает 24
  • factorial(5) завершается
    • возвращает 120

Пустая очередь.

Структуры данных и алгоритмы на Python

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

  • Метод оптимизации
  • Применяется преимущественно к рекурсии
  • Позволяет снизить сложность рекурсивных алгоритмов
  • Используется для:
    • Задач, которые можно разбить на подзадачи меньшего размера
    • Перекрывающихся подзадач
  • Решения подзадач сохраняются, что исключает повторные вычисления
    • Мемоизация
Структуры данных и алгоритмы на Python

Давайте потренируемся!

Структуры данных и алгоритмы на Python

Preparing Video For Download...