Короткий вступ до рекурсії в Javascript

Функція викликає себе, поки хтось не зупинить її.

Рекурсія може бути важкою для нових розробників. Можливо, це тому, що багато ресурсів навчають цього на алгоритмічних прикладах (Фібоначчі, пов'язані списки). Сподіваємось, цей твір напросто представить речі, використовуючи один простий приклад.

Основна ідея

Рекурсія - це коли функція викликає себе, поки хтось її не зупинить. Якщо ніхто не зупинить це, воно повториться (зателефонує) назавжди.

ні-це-це-патрік

Рекурсивні функції дозволяють виконувати одиницю роботи кілька разів. Це саме те, що for/whileдозволимо нам виконати! Однак іноді рекурсивні рішення є більш елегантним підходом до вирішення проблеми.

Функція зворотного відліку

Давайте створимо функцію, яка відлічує від заданого числа. Ми будемо використовувати його так.

countDownFrom(5); // 5 // 4 // 3 // 2 // 1 

І ось наш алгоритм вирішення цієї проблеми.

  1. Візьмемо один параметр, який називається number. Це наша вихідна точка.
  2. Перейдіть numberзнизу до 0, реєструючи кожен по дорозі.

Ми почнемо з forциклічного підходу, а потім порівняємо його з рекурсивним.

Імперативний підхід (петлі)

function countDownFrom(number) { for (let i = number; i > 0; i--) { console.log(i); } } countDownFrom(5); // 5 // 4 // 3 // 2 // 1 

Цей містить обидва алгоритмічні кроки.

  1. Візьміть один параметр, який називається number.
  2. Записати все від numberдо 0.

Рекурсивний підхід

function countDownFrom(number) { if (number === 0) { return; } console.log(number); countDownFrom(number - 1); } countDownFrom(5); // 5 // 4 // 3 // 2 // 1 

Цей теж проходить.

  1. Візьміть один параметр, який називається number.
  2. Записати все від numberдо 0.

Тож концептуально два підходи однакові. Однак вони виконують роботу по-різному.

Налагодження нашого імперативного рішення

Для більш наочного прикладу давайте додамо a debuggerу нашу циклічну версію та додамо її до Chrome Developer Tools.

function countDownFrom(number) { for (let i = number; i > 0; i--) { console.log(i); debugger; } } 

зворотний відлік

Подивіться, як він використовує додаткову змінну i, для відстеження поточного числа? У міру повторення iзменшується, врешті-решт потрапляючи 0та закінчуючи.

І в forциклі ми вказали "зупинити, якщо i > 0".

Налагодження нашого рекурсивного рішення

function countDownFrom(number) { if (number === 0) { return; } console.log(number); debugger; countDownFrom(number - 1); } 

відлік - від рекурсивного

Рекурсивна версія не потребує зайвих змінних для відстеження її прогресу. Зверніть увагу, як купу функцій ( стек викликів ) зростає під час повторення?

Це тому, що кожен виклик countDownFromдодає до стека, подаючи його number - 1. Роблячи це, ми numberкожного разу передаємо оновлене . Не потрібно зайвого штату!

Це головна різниця між двома підходами.

  1. Ітеративний використовує внутрішній стан (додаткові змінні для підрахунку тощо).
  2. Рекурсивний - ні, він просто передає оновлені параметри між кожним дзвінком.

Але як будь-яка версія знає, коли зупинятись?

Нескінченні петлі

Під час подорожей вас могли попереджати про страшну нескінченну петлю.

? THIS RUNS FOREVER, BE WARNED ? while (true) { console.log('WHY DID YOU RUN THIS?!' } ? THIS RUNS FOREVER, BE WARNED ? for (i = 0;;) { console.log('WHY DID YOU RUN THIS?!') } 

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

✅ This does not run forever x = 0; while (x < 3) { console.log(x); x++; } ✅ This does not run forever for (x = 0; x < 3; x++) { console.log(x); } 

В обох випадках ми реєструємо x, збільшуємо його і зупиняємося, коли воно стає 3. Наша countDownFromфункція мала схожу логіку.

// Stop at 0 for (let i = number; i > 0; i--) 

Знову ж таки, цикли потребують додаткового стану, щоб визначити, коли вони повинні зупинитися. Ось для чого xі iдля чого.

Нескінченна рекурсія

Рекурсія також представляє ту саму небезпеку. Неважко написати функцію самозв’язку, яка призведе до збоїв у роботі вашого браузера.

?THIS RUNS FOREVER, BE WARNED? function run() { console.log('running'); run(); } run(); // running // running // ... 

це-це-рекурсивно

Without a stopping condition, run will forever call itself. You can fix that with an if statement.

✅ This does not run forever function run(x) { if (x === 3) return; console.log('running'); run(x + 1); } run(0); // running // running // running // x is 3 now, we're done. 

Base case

This is known as the base case–our recursive countDownFrom had one.

if (number === 0) { return; } 

It's the same idea as our loop's stopping logic. Whichever approach you pick, always remember that at some point it needs to be stopped.

це-це-вам-потрібно-бути-зупиненим

Summary

  • Recursion is when a function calls itself until someone stops it.
  • It can be used instead of a loop.
  • If no one stops it, it'll recurse forever and crash your program.
  • A base case is a condition that stops the recursion. Don't forget to add them!
  • Loops use extra state variables for tracking and counting, while recursion only uses the provided parameters.

зникаючі петлі

Thanks for reading

Щоб отримати більше подібного вмісту, перегляньте //yazeedb.com. І, будь ласка, дайте мені знати, що ще ви хотіли б побачити! Мої DM відкриті в Twitter.

До наступного разу!