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

„За да разберем рекурсията, първо трябва да разберем рекурсията.“

Рекурсията може да бъде трудна за разбиране - особено за нови програмисти. В най-простата си форма рекурсивната функция е тази, която се извиква. Нека се опитам да обясня с пример.

Представете си, че отивате да отворите вратата на спалнята си и тя е заключена. Вашият тригодишен син се появява от ъгъла и ви уведомява, че е скрил единствения ключ в кутия. („Точно като него“, мислите си.) Закъснявате за работа и наистина трябва да влезете в стаята, за да вземете ризата си.

Отваряте полето само за да намерите ... още кутии. Кутии вътре в кутии. И не знаете кой има ключа! Трябва да вземете тази риза скоро, така че трябва да измислите добър алгоритъм, за да намерите този ключ.

Има два основни подхода за създаване на алгоритъм за този проблем: итеративен и рекурсивен. Ето и двата подхода като блок-схеми:

Кой подход ви се струва по-лесен?

Първият подход използва цикъл 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. Тъй като пет не е по-малко или равно на нула, отиваме към оператора else. Там отново извикваме функцията за обратно броене с числото четири (5–1 = 4?).

Ще влезем броя 4. Отново iе не по-малко от или равно на нула, за да можем да отидете на друго изявление и призив броене с 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-минутно видео, което направих за рекурсията. Тя трябва да засили тези концепции за рекурсия.

Заключение

Надявам се тази статия да ви донесе повече яснота относно рекурсията в програмирането. Тази статия се основава на урок от новия ми видео курс от Manning Publications, наречен Algorithms in Motion. Курсът (а също и тази статия) е базиран на невероятната книга Grokking Algorithms от Adit Bhargava. Той е този, който нарисува всички забавни илюстрации в тази статия.

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

Вземете 39% отстъпка от курса ми, като използвате код ' 39carnes '!

И накрая, за да разберете истински рекурсията, трябва да прочетете тази статия отново. ?