Структура данных - основы рекурсии

Алгоритмы

Представляю вашему вниманию перевод статьи Beau Carnes How Recursion Works - explained with flowcharts and a video .

«Для того чтобы понять рекурсию, надо сначала понять рекурсию»

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

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

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

Есть два основных подхода в создании алгоритма для решения данной проблемы: итеративный и рекурсивный. Вот блок-схемы этих подходов:

Какой подход для Вас проще?

В первом подходе используется цикл 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!") } } }

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

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

Граничный и рекурсивный случай

То, что Вам необходимо принять во внимание при написании рекурсивной функции – это бесконечный цикл, т.е. когда функция вызывает саму себя… и никогда не может остановиться.
Допустим, Вы хотите написать функцию подсчета. Вы можете написать ее рекурсивно на Javascript, к примеру:

// WARNING: This function contains an infinite loop! function countdown(i) { console.log(i) countdown(i - 1) } countdown(5); // This is the initial call to the function.

Эта функция будет считать до бесконечности. Так что, если Вы вдруг запустили код с бесконечным циклом, остановите его сочетанием клавиш «Ctrl-C». (Или, работая к примеру в CodePen, это можно сделать, добавив “?turn_off_js=true” в конце URL.)

Рекурсивная функция всегда должна знать, когда ей нужно остановиться. В рекурсивной функции всегда есть два случая: рекурсивный и граничный случаи. Рекурсивный случай – когда функция вызывает саму себя, а граничный – когда функция перестает себя вызывать. Наличие граничного случая и предотвращает зацикливание.

И снова функция подсчета, только уже с граничным случаем:

Function countdown(i) { console.log(i) if (i <= 1) { // base case return; } else { // recursive case countdown(i - 1) } } countdown(5); // This is the initial call to the function.

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

Сначала мы выведем цифру 5, используя команду Console.Log . Т.к. 5 не меньше или равно 1, то мы перейдем в блок else . Здесь мы снова вызовем функцию и передадим в нее цифру 4 (т.к. 5 – 1 = 4).

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

Стек вызовов

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

Я продемонстрирую Вам стек вызовов в действии, используя функцию подсчета факториала. 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 .

Нашли уже ключ?

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

Но в рекурсивном подходе нет стопки. Так как тогда алгоритм понимает в какой коробке следует искать? Ответ: «Стопка коробок» сохраняется в стеке. Формируется стек из наполовину выполненных обращений к функции, каждое из которых содержит свой наполовину выполненный список из коробок для просмотра. Стек следит за стопкой коробок для Вас!

И так, спасибо рекурсии, Вы наконец смогли найти свой ключ и взять рубашку!

Вы также можете посмотреть мое пятиминутное видео про рекурсию. Оно должно усилить понимание, приведенных здесь концепций.

Заключение от автора

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

Некоторые языки программирования позволяют функции вызывать себя. Этот метод известен как рекурсивный алгоритм. В рекурсии функция a вызывает непосредственно саму себя или вызывает функцию b , которая в свою очередь вызывает оригинальную функцию a . Функция a называется рекурсивной.

Пример — функция, вызывающая себя:

< 1) return; function(value - 1); printf("%d ",value); }

Пример — функция, которая вызывает другую функцию, которая в свою очередь, вызывает ее снова:

int function(int value) { if(value < 1) return; function(value - 1); printf("%d ",value); }

Свойства

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

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

Реализация

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

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

Фрейм стека хранит информацию о локальных переменных, формальных параметрах, адрес возврата, а также все сведения, передаваемые вызываемой функции.

Анализ рекурсии

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

Сложность по времени

Чтобы подсчитать время работы алгоритма на основе итераций, мы используем количество операций. С рекурсией все аналогично: мы пытаемся выяснить процессорное время, за которое выполняется рекурсивный вызов. Вызов функции 0(1) , следовательно (n) — количество рекурсивных вызовов, которые выполнит рекурсивная функция 0(n) .

Вычислительная сложность

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

Перевод статьи “Data Structure — Recursion Basics ” был подготовлен дружной командой проекта .

Хорошо Плохо

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