Кратко въведение в рекурсията в 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. Iterative използва вътрешно състояние (допълнителни променливи за броене и т.н.).
  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.

До следващия път!