Node'догу алгоритмдер: рекурсия, дарактар жана графтарды кыдыруу
Рекурсия, анын чыныгы баасы жана таза Node каражаттары менен дарактарды жана графтарды кантип моделдеп, кыдыруу.
Map/Set жана fs/promises орто курстан. Бул сабактын аягында сиз мына буларды жасай аласыз:
- туура базалык учуру бар рекурсивдик функция жазуу жана анын чакыруу стеги тууралуу ой жүгүртүү;
- рекурсиянын компромисстерин атоо жана мемоизацияны ал чын эле жардам берген жерде колдонуу;
- Node'до даракты жана графты моделдөө жана каталог дарагын кыдыруу;
- көз карандылыктарды топологиялык тартип менен чечүү жана циклдерди аныктоо;
- кеңдиги боюнча (BFS) жана тереңдиги боюнча (DFS) издөөнү ишке ашыруу жана тандоо.
1. Рекурсия: базалык жана рекурсивдик учур
Рекурсивдик функция ошол эле маселенин кичирээк вариантына өзүн чакырат. Ар бир туура рекурсиянын так эки бөлүгү бар: рекурсиясыз түз жооп кайтарган базалык учур, жана бир аз иш жасап, анан базага жакыныраак нерсеге өзүн чакырган рекурсивдик учур.
function factorial(n) {
if (n <= 1) return 1; // base case: stop recursing
return n * factorial(n - 1); // recursive case: shrink toward the base
}
console.log(factorial(5)); // 120Муну келишим катары окуңуз: factorial(5) factorial(4)'тин туура болушуна ишенет, 5ке көбөйтөт жана кайтарат. Базалык учур (n <= 1) — бул түшүүнү токтоткон нерсе. Аны алып салсаңыз, функция эч качан бүтпөйт.
Салыштыруу. Рекурсия — бул матрёшка. Куурчактарды санаш үчүн сырткысын ачасыз (бир аз иш), анан ичиндеги куурчакка ошол эле суроону бересиз (рекурсивдик чакыруу). Ачылбаган эң кичине бүтүн куурчак — бул базалык учур; ансыз сиз түбөлүк ачмаксыз.
Рекурсия дайындардын өзү белгисиз тереңдикке салынганда жаркырайт — папкалар ичиндеги папкалар, же жоопторго жооптору бар комментарий бутагы. Жалпак for цикли «муну ар бир баланын үчүн кайтала, канчалык терең кетсе да» дегенди оңой билдире албайт; рекурсия — билдире алат.