Знакомимся с рекурсией

0
746
views

Перевод первой части статьи «Recursion Demystified».

Рекурсия

«Чтобы понять рекурсию, нужно сначала понять рекурсию».

Бред какой-то, правда?

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

Что такое рекурсия?

Как бы вы объяснили рекурсию 4-летнему ребенку? Это довольно известный вопрос для собеседований, в интернете можно найти множество вариантов ответов.

Если бы мне пришлось объяснять рекурсию четырехлетке, я бы объяснил ее кому-то на год младше себя. А он пускай бы объяснил кому-то на год младше его самого. И пускай бы все объясняли рекурсию по цепочке, пока 5-летний не объяснил бы ее 4-летнему. Готово. (Источник — reddit).

Если говорить о программировании, то рекурсия это функция, вызывающая саму себя:

def random_function(n):
		if n == 0: return
		random_function(n - 1)

Приведенная выше функция сама по себе бесполезна, однако демонстрирует понятие рекурсии. Рекуррентное соотношение здесь можно выразить следующей формулой:

T(N) = T(N - 1) + O(1)

Это означает, что выполнение вызова random_function(n) не сможет продолжиться, пока не завершится вызов random_function(n-1), и так далее.

По сути, мы откладываем выполнение текущего состояния функции, пока другой вызов той же функции не завершится и не вернет результат.

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

Стек рекурсии

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

Но вместо того чтобы пытаться вникнуть в это старое определение, мы рассмотрим несколько применений рекурсии. Это должно прояснить ситуацию.

Факториал числа

Давайте рассмотрим нахождение факториала числа. Но прежде давайте вспомним, что собой представляет факториал и как он вычисляется.

factorial(N) = 1 * 2 * 3 * .... * N - 1 * N

Проще говоря, факториал числа это просто произведение всех чисел от 1 до N.

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

Но если приглядеться, вы заметите, что для вычисления факториала можно применить рекурсивную структуру.

factorial(N) = N * factorial(N - 1)

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

Шаги рекурсивной функции для вычисления факториала
Проверка правильности вычислений

Как видно по рисункам, наша рекуррентная формула вычисления факториала верна.

factorial(N) = N * factorial(N - 1)

Взгляните на пример кода на Python для рекурсивного нахождения факториала числа:

def factorial(N):
    if N == 1:
        return 1
    return N * factorial(N - 1)

Этот пример был довольно прост. Давайте рассмотрим чуть более сложный пример для демонстрации концепции рекурсии.

Последовательность Фибоначчи

Вы, должно быть, знакомы с последовательностью чисел Фибоначчи.

1 1  2   3     5           8                       13 ….. 

Для тех, кто не в курсе, кратко поясню. В последовательности Фибоначчи каждое число представляет собой сумму двух предыдущих чисел, а первые два числа это либо 0 и 1, либо 1 и 1.

Давайте рассмотрим формулу для вычисления n-го числа Фибоначчи.

F(n) = F(n - 1) + F(n - 2)
где F(1) = F(2) = 1

Явно видно, что определение последовательности Фибоначчи рекурсивно по своей природе, поскольку n-е число зависит от двух предыдущих чисел. Это означает, что задачу можно разделить на меньшие подзадачи, а это рекурсия. Вот пример кода для решения этой задачи:

def find_fibonacci(N):
	if N == 1 or N == 2:
		return 1
	return find_fibonacci(N - 1) + find_fibonacci(N - 2)

Каждая рекурсивная задача имеет две необходимые вещи:

  1. Рекуррентное соотношение, определяющее состояния задачи и то, как основная задача может быть разделена на меньшие подзадачи. Сюда также входит базовый случай для прекращения рекурсии.
  2. Дерево рекурсии, демонстрирующее несколько первых вызовов рассматриваемой функции (если не все). Взгляните на дерево рекурсии для рекурсивного соотношения последовательности Фибоначчи:
Дерево рекурсии
Дерево рекурсии

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

Листьями этого дерева рекурсии будут fibonacci(1) или fibonacci(2), которые представляют собой базовые случаи для этой рекурсии.

Теперь, когда у нас есть базовое понимание рекурсии, рекуррентного соотношения и дерева рекурсии, давайте перейдем к чему-то более интересному — к примерам!

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

Высота дерева

Для простоты мы будем рассматривать только бинарное дерево. Итак, бинарное дерево это древовидная структура данных, в которой каждый узел имеет максимум двух потомков. Один из узлов дерева считается его корнем, например здесь корнем является узел «А»:

Дерево с корневым узлом «А»

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

Высота дерева это длина самого длинного пути от корня к листу в этом дереве.

Таким образом, если рассматривать приведенную выше схему и исходить из того, что корнем этого дерева является узел «А», самый длинный путь это A → C → E → G → I . То есть, высота дерева — 5 (если считать количество узлов) или 4 (если считать количество ребер) самого длинного пути.

А теперь забудьте обо всем дереве и сосредоточьтесь на его выделенном фрагменте:

Поддеревья

На этой схеме представлено дерево в виде его поддеревьев. Структуры справа и слева от узла «А» сами по себе тоже являются бинарными деревьями, только они меньше и корневыми в них являются другие узлы. Но это все равно бинарные деревья.

Как информация, полученная от этих двух поддеревьев, может помочь нам найти высоту основного дерева с корнем в узле «А»?

Если мы знаем высоту левого поддерева (скажем, это h1) и высоту правого (скажем, h2), мы можем сказать, что высота основного дерева это высота самого высокого из двух поддеревьев +1 (единица — для узла «А»). Формула этого рекуррентного соотношения выглядит следующим образом:

height(root) = max(height(root.left), height(root.right)) + 1

Итак, это формула для рекурсивного вычисления высоты бинарного дерева. Фокус здесь на слове «бинарный», потому что мы использовали только двух потомков узла root — root.left и root.right. Но это рекуррентное соотношение легко расширить для любого дерева. Давайте посмотрим на этот код:

"""
  class Node:
    def __init__(self, x):
      self.left = None
      self.right = None
      self.val = x
"""

def binary_tree_height(node):
  if not node:
    return 0
  
  left_subtree_height = binary_tree_height(node.left)
  right_subtree_height = binary_tree_height(node.right)
  
  return max(left_subtree_height, right_subtree_height) + 1

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

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

Количество узлов дерева

Для простоты мы опять будем говорить о бинарном дереве, но применяемый алгоритм и подход можно расширить для любого дерева.

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

Взгляните на эту схему:

Количество узлов в поддеревьях

Мы уже знаем, что дерево можно разбить на два меньших поддерева. Мы опять спрашиваем себя: «Как информация, полученная из двух поддеревьев, может помочь нам найти общее количество узлов в дереве с корнем в узле «А»?»

Ну, если нам известно количество узлов в левом и правом поддеревьях, мы можем попросту их сложить и добавить узел-корень. Это даст нам общее количество узлов. Формула будет следующей:

number_of_nodes(root) = number_of_nodes(root.left) +
number_of_nodes(right) + 1

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


"""
  class Node:
    def __init__(self, x):
      self.left = None
      self.right = None
      self.val = x
"""

def number_of_nodes(node):
  if not node:
    return 0
  
  left_subtree_nodes = number_of_nodes(node.left)
  right_subtree_nodes = number_of_nodes(node.right)
  
  return left_subtree_nodes + right_subtree_nodes + 1

Теперь, рассмотрев пару простых примеров с бинарным деревом, давайте перейдем к чему-то менее тривиальному.

Сортировка слиянием

Дан массив чисел:

4 2 8 9 1 5 2

Нужно придумать, как рассортировать их в возрастающем или убывающем порядке.

Существует много известных методов сортировки: быстрая сортировка, пирамидальная сортировка, поразрядная сортировка и т. д. Но в данном примере мы рассмотрим сортировку слиянием.

Вероятно, вам известен принцип «разделяй и властвуй», так что дальнейшее объяснение может показаться вам знакомым.

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

Допустим, наш исходный массив будет разделен на две половины, и обе они будут отсортированы. Сможем мы как-то использовать это для сортировки всего массива?

Это основная идея. Задача сортировки массива может быть разбита на две меньшие подзадачи:

  1. сортировка двух половинок массива;
  2. использование отсортированных половинок для получения полностью отсортированного массива.

Красота рекурсии в том, что не нужно волноваться о том, как получить две отсортированные половины и какую логику применять для этого. Поскольку это рекурсия, обе половины массива будут отсортированы при помощи вызова того же метода merge_sort. Все, что нам нужно, – сфокусироваться на том, что необходимо сделать с уже отсортированными частями.

Обратимся к коду:

def merge_sort(arr, left, right):
	if left >= right:
		return []
	if left == right - 1:
		return [arr[left]]
	
	mid = left + (right - left) / 2
	left_sorted_half = merge_sort(arr, left, mid)
	right_sorted_half = merge_sort(arr, mid, right)	

Здесь мы доверяем нашему старому другу — рекурсии — и исходим из того, что left_sorted_half и right_sorted_half на самом деле будут двумя отсортированными половинами исходного массива.

Что дальше?

Вопрос в том, как их скомбинировать, чтобы получить целый массив.

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

Пусть L и R будут нашими отсортированными половинами. 
Пусть ans будет комбинированным отсортированным массивом. 
 l = 0 // Указатель для левой половины
 r = 0 // Указатель для правой половины
 a = 0 // Указатель для массива ans 
 while l < L.length and r < R.length {
       if L[l] < R[r] {
            ans[a] = L[l]
            l++
        } else {
            ans[a] = R[r]
            r++
       }
 } 
 copy remaining array portion of L or R, whichever was longer, into ans.

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

В результате сортировка слиянием выглядит следующим образом:

def merge_sort(arr, left, right):
	if left >= right:
		return []
	if left == right - 1:
		return [arr[left]]
	
	mid = left + (right - left) / 2
	left_sorted_half = merge_sort(arr, left, mid)
	right_sorted_half = merge_sort(arr, mid, right)
	
	l = 0
	r = 0
	ans = []
	while l < len(left_sorted_half) and r < len(right_sorted_half):
		if left_sorted_half[l] < right_sorted_half[r]:
			ans.append(left_sorted_half[l])
			l += 1
		else:
			ans.append(right_sorted_half[r])
			r += 1
	
	if l < len(left_sorted_half):
		ans.extend(left_sorted_half[l:])
	else:
		ans.extend(right_sorted_half[r:])
	return ans	

Во второй части статьи мы разберем еще один, самый сложный пример.

ОСТАВЬТЕ ОТВЕТ

Please enter your comment!
Please enter your name here