Как работает рекурсия - объяснение с рисунками и видео

---

рекурсия цикл

Все иллюстрации в этой статье Adit Bhargava

"Чтобы понять рекурсию, сперва нужно понять рекурсию."

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

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

Вы открываете коробку в поисках ключа... много коробок. Коробки внутри коробок. И вы не знаете в какой именно из них ключ! Рубашка нужна очень срочно, так что вам нужно придумать оптимальный алгоритм поиска ключа.

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

Какой из способов вам кажется проще?

Первое решение использует цикл while. Пока куча не пуста, берем коробку и смотрим что в ней. Ниже представлен псевдо-код на JavaScript, который показывает что происходит. Псевдокод написан в виде кода, но больше походит на человеческую речь.

function look_for_key(main_box) {
  let pile = main_box.make_a_pile_to_look_through();
  while (pile is not empty) {
    box = pile.grab_a_box();
    for (item in box) {
      if (item.is_a_box()) {
        pile.append(item)
      } else if (item.is_a_key()) {
        console.log("found the key!")
      }
    }
  }
}

Второй вариант использует рекурсию. Помните, что рекурсия - это когда функция вызывает сама себя? Этой второй вариант псевдо-кода.

function look_for_key(box) {
  for (item in box) {
    if (item.is_a_box()) {
      look_for_key(item);
    } else if (item.is_a_key()) {
      console.log("found the key!")
    }
  }
}

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

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

Базовый и рекурсивный случай

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

Например, вам возможно необходимо написать функцию обратного отсчета. Вы можете написать ее через рекурсию:

// ВНИМАНИЕ: Эта функция содержит бесконечный цикл!
function countdown(i) {
  console.log(i)
  countdown(i - 1)
}
countdown(5);    // Исходный вызов функции.

Эта функция будет вести отсчет бесконечно. Если вы случайно запустили код с бесконечным циклом, то вы можете нажать "Ctrl-C", чтобы остановить скрипт. Или если вы, как и я, иногда используете CodePen, то вы должны добавить в конец url:

?turn_off_js=true

Рекурсивная функция всегда скажет, когда закончит повторять себя. Должно быть две части в рекурсивной функции: рекурсивная и основная. Рекурсивная часть - это вызов функции самой себя. Базовая часть - это когда заканчивает вызывать себя. Это предотвращает работу в бесконечном цикле.

Ниже представлена снова обратного отсчета с основной частью:

function countdown(i) {
  console.log(i)
  if (i <= 1) {  // основная часть
    return;  
  } else {       // рекурсивная часть
    countdown(i - 1)
  }
}
countdown(5);    // первый запуск функции.

Может быть не совсем ясно, что происходить в данной функции. Поэтому последовательно рассмотрим что происходит если вызвать функцию в параметром `5`.

Мы начинаем с вывода числа `5` через console.log. Так как значение 5 не меньше и не равно нулю, то проходим по ветке `else`. И здесь вызываем функцию countdown снова с параметром 5 (5-1=4????).

Далее выводится значение 4 в лог. И снова, значение `i` не меньше и не равно нулю, поэтому снова попадаем на ветку `else` и снова вызываем функцию с числом 3. Это продолжается то тех пор, пока значение `i` не станет равно нулю. Когда это произойдет, то в лог выведется нуль и значение `i` попадает под условие меньше или равно нулю. Наконец мы добрались до `return` и выходим из функции. 

Стек вызовов

Рекурсивные функции используют так называемый "стек вызовов". Когда программа вызывает функцию, эта функция переходит наверх стека. Это подобно стопке книг. Вы добавляете книги по одной. Потом, когда вы готовы взять какую-то из них, то берете всегда верхнюю.

Покажу вам стек вызова в в действии на примере функции `factorial`. Функцию `factorial(5)` можно записать как 5! и вычисляется это так:

5! = 5 * 4 * 3 * 2 * 1

Это рекурсивная функция вычисляет факториал числа:

function fact(x) {
  if (x == 1) {  
    return 1;  
  } else {      
    return x * fact(x-1);
  }
}

Сейчас давайте посмотрим что происходит если вызвать `fact(3)`. Иллюстрация ниже показывает как изменяется стек, строка за строкой.

Верхняя строка в стеке говорит вам, что вызов `fact`запущен.

Отметим как каждый вызов `fact` имеет собственную копию `x`. Это очень важно для работы рекурсии. И вы не имеете доступа к разным копиям `x` функций.

Вы уже нашли ключ?

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

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

И спасибо рекурсии за то, что вы в итоге нашли ключ и получили вашу рубашку! :-)

Вы также можете просмотреть это 5-минутное видео, которое я сделал о рекурсии. Оно должно закрепить у вас представление о рекурсии.

Заключение

Надеюсь эта статья дала вам больше ясности о рекурсии в программировании. Эта статья основана на уроке из моего нового видеокурса Алгоритмы в действии. Курс (а также эта статья), основаны на удивительной книге Grokking Algorithms Adit Bhargava. Он первый, кто изобразил все это в веселых иллюстрациях к этой статье.

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

Получите скидку 50% на мой курс по промокоду vlcarnes до 31 августа!

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

Перевод статьи How Recursion Works—explained with flowcharts and a video

 

// mac-test.js 
window.navigator.appVersion.match('Mac') !== null
> true

// У ваc Mac? И это круто!
// Если нужен ремонт,
// то советую
// http://macmachine.ru
// спросить Александра