Річ у тому, що в першому випадку у вас ліниве, а в другому - енергійне обчислення відповіді. Це означає, що елементи вихідної послідовності в енергійному випадку обчислюються всі і відразу, а в ледачому випадку - тільки коли запитані і тільки ті, що запитані.
Подивімося, де з практичного боку є різниця.
Для випадку ледачого обчислення вся послідовність не присутня повністю в пам'яті. Це означає, що при обробці по елементах у нас не виділяється пам'ять, і зберігається cache locality:
IEnumerable GenerateHugeSequenceLazy()
{
for (int i = 0; i < 1000000; i++)
yield return 13 * i;
}
IEnumerable GenerateHugeSequenceEager()
{
var result = new List();
for (int i = 0; i < 1000000; i++)
result.Add(13 * i);
return result;
}
Обчислюємо функцію на всій послідовності, порівнюємо витрата пам'яті:
var seqLazy = GenerateHugeSequenceLazy();
// вичисляємо максимум вручну
var max = 0;
foreach (var v in seqLazy)
if (v > max)
max = v;
var memLazy = GC.GetTotalMemory(forceFullCollection: false);
var seqEager = GenerateHugeSequenceEager();
// вичисляємо максимум вручну
max = 0;
foreach (var v in seqEager)
if (v > max)
max = v;
var memEager = GC.GetTotalMemory(forceFullCollection: false);
Console.WriteLine($"Memory footprint lazy: , eager: ");
Результат:
Memory footprint lazy: 29868, eager: 6323088
Далі, у нас досить великі відмінності в розумінні операцій. Енергійні обчислення проводяться в момент виклику функції, в той час, як ледачі обчислення відбуваються в момент, коли ви користуєтеся результатом. А значить, для реального обчислення ледачої послідовності стан аргументів буде взято на момент перерахування. Ось приклад:
IEnumerable DoubleEager(IEnumerable seq)
{
var result = new List();
foreach (var e in seq)
result.Add(e * 2);
return result;
}
IEnumerable DoubleLazy(IEnumerable seq)
{
foreach (var e in seq)
yield return e * 2;
}
Дивимося на відмінності:
var seq = new List() { 1 };
var eagerlyDoubled = DoubleEager(seq);
var lazilyDoubled = DoubleLazy(seq);
Console.WriteLine("Eager: " + string.Join(" ", eagerlyDoubled));
Console.WriteLine("Lazy : " + string.Join(" ", lazilyDoubled));
// виведе обидва рази 2, поки відмінностей немає
seq.Add(2); // змінюємо вихідну послідовність
Console.WriteLine("Eager: " + string.Join(" ", eagerlyDoubled)); // 2
Console.WriteLine("Lazy : " + string.Join(" ", lazilyDoubled)); // 2 4
Оскільки ліниве обчислення відбувається при перерахуванні, ми бачимо, що при зміні послідовності лінива версія підхоплює зміни.
Інший приклад. Подивимося, що буде, якщо ми не обчислюємо всю послідовність. Обчислимо одну і ту ж послідовність енергійно та ліниво:
IEnumerable Eager10()
{
Console.WriteLine("Eager");
int counter = 0;
try
{
var result = new List();
for (int i = 0; i < 10; i++)
{
Console.WriteLine($"Adding: ");
counter++;
result.Add(i);
}
return result;
}
finally
{
Console.WriteLine($"Eagerly computed: ");
}
}
IEnumerable Lazy10()
{
Console.WriteLine("Lazy");
int counter = 0;
try
{
for (int i = 0; i < 10; i++)
{
Console.WriteLine($"Adding: ");
counter++;
yield return i;
}
}
finally
{
Console.WriteLine($"Lazily computed: ");
}
}
Беремо тільки 2 елементи з результату:
foreach (var e in Eager10().Take(2))
Console.WriteLine($"Obtained: ");
foreach (var e in Lazy10().Take(2))
Console.WriteLine($"Obtained: ");
foreach (var e in Lazy10())
{
Console.WriteLine($"Obtained: ");
if (e == 1)
break;
}
Бачите різницю? Лінивий варіант прогнав цикл всього два рази, і не обчислював «хвіст» послідовності.
Ще одна різниця між випадками - коли повідомляються помилки. У разі енергійного обчислення вони повідомляються відразу. У разі ледачого - лише при перерахуванні результату. приклад:
IEnumerable CheckEagerly(int value)
{
if (value == 0)
throw new ArgumentException("value cannot be 0");
return new List { value };
}
IEnumerable CheckLazily(int value)
{
if (value == 0)
throw new ArgumentException("value cannot be 0");
yield return value;
}
Застосовуємо try / catch:
Console.WriteLine("Eager:");
IEnumerable seqEager = null;
try
{
seqEager = CheckEagerly(0);
}
catch (ArgumentException)
{
Console.WriteLine("Exception caught");
}
if (seqEager != null)
foreach (var e in seqEager)
Console.WriteLine(e);
Console.WriteLine("Lazy:");
IEnumerable seqLazy = null;
try
{
seqLazy = CheckLazily(0);
}
catch (ArgumentException)
{
Console.WriteLine("Exception caught");
}
if (seqLazy != null)
foreach (var e in seqLazy)
Console.WriteLine(e);
Отримуємо результат:
Eager:
Exception caught
Lazy:
Unhandled Exception: System.ArgumentException: value cannot be 0
at Program.d__3.MoveNext() in ...\Program.cs:line 59
at Program.Run() in ...\Program.cs:line 45
at Program.Main(String[] args) in ...\Program.cs:line 13
Для того, щоб отримати «найкраще з обох світів», тобто, ліниве обчислення, але енергійну перевірку аргументів, найпростіше розділити функцію на дві: енергійну перевірку і ліниве обчислення без перевірки. Для сучасних версій C# зручно використовувати вкладені функції:
IEnumerable CheckEagerlyEnumerateLazily(int value)
{
if (value == 0)
throw new ArgumentException("value cannot be 0");
return Impl();
IEnumerable Impl()
{
yield return value;
}
}
Перевіряємо:
Console.WriteLine("Recommended way:");
IEnumerable seqLazy = null;
try
{
seqLazy = CheckEagerlyEnumerateLazily(0);
}
catch (ArgumentException)
{
Console.WriteLine("Exception caught");
}
if (seqLazy != null)
foreach (var e in seqLazy)
Console.WriteLine(e);
і отримуємо
Recommended way:
Exception caught
Ще один випадок відмінності - залежність від зовнішніх даних в процесі обчислення. Наступний код намагається впливати на обчислення, змінюючи глобальний стан. (Це не дуже хороший код, не робіть так в реальних програмах!)
bool evilMutableAllowCompute;
IEnumerable EagerGet5WithExternalDependency()
{
List result = new List();
for (int i = 0; i < 5; i++)
{
if (evilMutableAllowCompute)
result.Add(i);
}
return result;
}
IEnumerable LazyGet5WithExternalDependency()
{
for (int i = 0; i < 5; i++)
{
if (evilMutableAllowCompute)
yield return i;
}
}
Використовуємо:
Console.WriteLine("Eager:");
evilMutableAllowCompute = true;
foreach (var e in EagerGet5WithExternalDependency())
{
Console.WriteLine($"Obtained: ");
if (e > 0)
evilMutableAllowCompute = false;
}
Console.WriteLine("Lazy:");
evilMutableAllowCompute = true;
foreach (var e in LazyGet5WithExternalDependency())
{
Console.WriteLine($"Obtained: ");
if (e > 0)
evilMutableAllowCompute = false;
}
Для каталогів можна виключити один або кілька каталогів за допомогою параметра --exclude-dir. Наприклад, ця команда виключить директорії dir1/, dir2/ а також ті що відповідають *.dst/:
Модель це кінцевий файл який отримали в результаті тренування на великій кількості даних та GPU. В ній містяться дані які "запам'ятала" нейронна мережа (зв’язки між словами та фразами) і на основі цих даних може генерувати відповіді на питання. Це не зовсім те що потрібно для пошуку по сайту, та і для навчання на своїх даних треба багато потужних GPU.
function removeElement(nums, val) {
let k = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== val) {
nums[k] = nums[i];
k++;
}
}
nums.length = k;
return k;
}
До вищесказаного можна додати наступне. Далеко не всі пулл-реквести приймаються розробниками. Тут потрібно дотримати ряд правил:
Пулл-реквест (ПР) повинен бути добре оформлений і містити вичерпний опис.
Звичайне правило, один баг - один ПР, одна фіча - один ПР. Не потрібно намагатися запхати відразу купу всього.
Дуже важливо дотримуватися Code Style того проєктe, для якого ви робите ПР. Нехай навіть він здається вам протиприродним (наприклад ви завжди робите відступи у вигляді 4 пробіли, а в проєкті таби).
Не потрібно боятися робити ПР-и, адже допомогти можна навіть в дрібниці. Наприклад ви знайшли помилку перекладу в readme файлі або вам здається що якийсь опис фічі можна зрозумілішо перефразувати.
На гітхабі мільйони проєктів, які живуть виключно на ентузіазмі творців, хороші ПР-и дуже добре стимулюють цей ентузіазм)
Різниця між PUT і POST - це питання семантики. Оскільки для операцій використовуються різні дієслова, то і сенс у них повинен бути різним.
Уявіть, що ваш сервіс оперує поняттями блокнот (notebook) і запис (post). Один блокнот може містити безліч записів.
Для додавання нового запису в блокнот c ідентифікатором id ви будете використовувати метод POST з URL mydomain/notebooks/id/. Ваш сервіс, орієнтуючись на метод POST, сам присвоїть потрібний ідентифікатор запису, додасть її в блокнот і поверне вам URL створеного запису (для доступу до запису по GET або для видалення по DELETE). При цьому добре б повернути клієнту URL створеної записи.
Припустимо, запис з ідентифікатором post-id вже створено і він доступний по URL mydomain/notebooks/id/posts/post-id. Але клієнт (власник запису) виправив в ній помилку і хоче перезаписати її. Для цього він використовує метод PUT з URL mydomain/notebooks/id/posts/post-id і передає оновлений запис в тілі запиту. Ваш сервіс, орієнтуючись на метод PUT видаляє старий запис і записує новий, при цьому він доступний за тим же URL.
Звичайно, ніхто не заважає вам завжди використовувати метод POST (наприклад HTML 4 дозволяв використовувати тільки методи GET і POST). Але все ж варто дотримуватися рекомендацій з метою однакового трактування методів усіма розробниками.
Рекомендується використовуватися метод POST для створення підлеглого ресурсу (дочірнього по відношенню до іншого ресурсу; приклад блокнота і записи якраз дуже підходить).
Основна ідея - поліпшення переносимості. Не гарантується, що на різних системах виконуваний файл буде лежати по шляху, який вказаний в shebang.
Використання env дозволяє знизити цей ризик за рахунок запуску команди на основі даних зі змінної середовища PATH
Більш того, якщо з яких-небудь причин замість стандартного файлу користувач хоче використовувати свій, то йому достатньо додати шлях до цього файлу в PATH без необхідності виправлення скриптів:
В наведеному вище прикладі я скопіював bash до себе в домашню директорію (перейменувавши при цьому файл в python), додав шлях в PATH і запустив python за допомогою env, яка запустила bash, тому що знайшла його раніше.
Ще одним прикладом є використання віртуальних оточень при розробці на Python (virtualenv). Оскільки вони також перебивають PATH, env дозволяє використовувати потрібну версію виконуваного файлу:
~ $ workon black-box-challenge-2016-py2
~ (venv:black-box-challenge-2016-py2) $ env python
Python 2.7.11 (default, Mar 31 2016, 06:18:34)
[GCC 5.3.0] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> print sys.executable
/home/soon/.virtualenvs/black-box-challenge-2016-py2/bin/python
>>>
Я б рекомендував вибирати серед найпопулярніших дистрибутивів: Ubuntu, Mint, Fedora, Manjaro.
Вибирайте яка графічна оболонка вам більше подобається (KDE, Gnome, Mate, Cinnamon, Unity, Pantheon, Xfce) і далі вибирайте з топових дистрибутивів які йдуть з цією оболонкою
Знайдіть індекс елемента масиву, який потрібно видалити, за допомогою indexOf, а потім видаліть цей індекс за допомогою splice.
const array = [2, 5, 9];
console.log(array);
const index = array.indexOf(5);
if (index > -1) { // only splice array when item is found
array.splice(index, 1); // 2nd parameter means remove one item only
}
// array = [2, 9]
console.log(array);
Другим параметром splice є кількість елементів, які потрібно видалити. Зауважте, що splice модифікує масив на місці та повертає новий масив, що містить елементи, які було видалено.
У випадку мовних моделей B означає мільярд, тобто 11B це модель яка містить 11 мільярдів зв'язків (в реальності там трохи складніше). І так, чим більше в моделі параметрів тим більше треба пам'яті щоб запустити модель.
Алгоритмічна рекурсія - це за визначенням алгоритм, побудований зі стратегії Розділяй та володарюй (Divide-and-Conquer), в якому для зберігання підзадач використана LIFO структура даних, тобто, попросту кажучи, стек.
У таких алгоритмів натуральним чином є прямий хід, коли задача розбивається на дрібніші підзадачі, які заносяться в стек. Потім підзадачі витягуються зі стека по одній і вирішуються за таким же принципом, тобто розбиваються на ще дрібніші підзадачі. Розбиття триває до тих пір, поки підзадача не стане розв'язуватися тривіально.
А також у рекурсивних алгоритмів є зворотний хід, коли все дрібніші підзадачі вже вирішені і їх рішення тепер можна об'єднати в рішення більше завдання.
Наявність зворотного ходу (backtracking) - відмінна риса саме рекурсивних алгоритмів. Тобто в рекурсії завжди є зворотний хід. Ось, власне, "при чому тут рекурсія".
Не всім рекурсивним алгоритмам потрібен цей зворотний хід - деяким алгоритмам просто нічого не потрібно робити на зворотному ході. Але сам процес зворотного ходу в рекурсивному алгоритмі завжди присутній, хай навіть і незримо.
Тому якщо ви розглядаєте якийсь рекурсивний алгоритм (перебору або чого-небудь ще), то там завжди обов'язково буде і "повернення" (тобто зворотний хід). А вже як він використовується в вашому алгоритмі та чи використовується взагалі - залежить від алгоритму.
У рекурсивному алгоритмі розставлення N ферзів на шахівниці, підзадачею є завдання розставлення m ферзів що залишилися (m < = N), коли перші N - m ферзів вже якось розставлені. Зворотний хід в цьому алгоритмі використовується тоді, коли ми раптом з'ясували, що підзадача не має рішення - ми повертаємо цей результат на попередній рівень рекурсії в процесі зворотного ходу і тим самим говоримо йому, що треба спробувати якийсь інший варіант розставлення N - m перших ферзів. А також, якщо вам доручено знайти всі можливі розстановки (а не якусь одну), зворотний хід рекурсії буде використовуватися для тих же цілей незалежно від того, чи успішно вирішена підзадача, чи ні.
Відмінності насправді кардинальні.
Річ у тому, що в першому випадку у вас ліниве, а в другому - енергійне обчислення відповіді. Це означає, що елементи вихідної послідовності в енергійному випадку обчислюються всі і відразу, а в ледачому випадку - тільки коли запитані і тільки ті, що запитані.
Подивімося, де з практичного боку є різниця.
Для випадку ледачого обчислення вся послідовність не присутня повністю в пам'яті. Це означає, що при обробці по елементах у нас не виділяється пам'ять, і зберігається cache locality:
Обчислюємо функцію на всій послідовності, порівнюємо витрата пам'яті:
Результат:
Далі, у нас досить великі відмінності в розумінні операцій. Енергійні обчислення проводяться в момент виклику функції, в той час, як ледачі обчислення відбуваються в момент, коли ви користуєтеся результатом. А значить, для реального обчислення ледачої послідовності стан аргументів буде взято на момент перерахування. Ось приклад:
Дивимося на відмінності:
Оскільки ліниве обчислення відбувається при перерахуванні, ми бачимо, що при зміні послідовності лінива версія підхоплює зміни.
Інший приклад. Подивимося, що буде, якщо ми не обчислюємо всю послідовність. Обчислимо одну і ту ж послідовність енергійно та ліниво:
Беремо тільки 2 елементи з результату:
Отримуємо такий висновок на консоль:
Бачите різницю? Лінивий варіант прогнав цикл всього два рази, і не обчислював «хвіст» послідовності.
Ще одна різниця між випадками - коли повідомляються помилки. У разі енергійного обчислення вони повідомляються відразу. У разі ледачого - лише при перерахуванні результату. приклад:
Застосовуємо try / catch:
Отримуємо результат:
Для того, щоб отримати «найкраще з обох світів», тобто, ліниве обчислення, але енергійну перевірку аргументів, найпростіше розділити функцію на дві: енергійну перевірку і ліниве обчислення без перевірки. Для сучасних версій C# зручно використовувати вкладені функції:
Перевіряємо:
і отримуємо
Ще один випадок відмінності - залежність від зовнішніх даних в процесі обчислення. Наступний код намагається впливати на обчислення, змінюючи глобальний стан. (Це не дуже хороший код, не робіть так в реальних програмах!)
Використовуємо:
Результат:
Ми бачимо, що зміна глобальних даних навіть після формального відпрацювання ледачої функції може впливати на обчислення.
(Це ще один аргумент на користь того, що функціональне програмування і мутабельний стан погано поєднуються.)
Поки що так. Відвідувачів на сайті ще не дуже багато, треба з чогось починати :)
Виконайте наступне:
-r
або-R
- рекурсивний пошук,-n
- вивести номер рядка-w
пошук цілого слова.-l
(нижній регістр L) можна додати, щоб просто вказати ім'я відповідного файлу.Також можна використовувати,
--exclude
,--include
,--exclude-dir
. Ці прапори можуть бути використані для ефективного пошуку:Ця команда буде здійснювати пошук лише у тих файлах з розширенням
.c
або.h
:Ця команда виконає пошук у всіх файлах, за виключенням тих що закінчуються розширенням
.o
:Для каталогів можна виключити один або кілька каталогів за допомогою параметра
--exclude-dir
. Наприклад, ця команда виключить директоріїdir1/
,dir2/
а також ті що відповідають*.dst/
:Для отримання додаткових опцій перевірте
man grep
.В perl6 це можна зробити ось так
Якщо проблема програмна, то варто перевірити
/var/log/syslog
таjournalctl
, там має бути видно що останнє запускалося.Якщо проблема апаратна, то ядро може падати в Kernel panic, для перевірки необхідно підключити монітор і можливо буде зрозуміла причина.
Ось приклад розмови GPT між собою
Модель це кінцевий файл який отримали в результаті тренування на великій кількості даних та GPU. В ній містяться дані які "запам'ятала" нейронна мережа (зв’язки між словами та фразами) і на основі цих даних може генерувати відповіді на питання. Це не зовсім те що потрібно для пошуку по сайту, та і для навчання на своїх даних треба багато потужних GPU.
Ось функція яка має вирішити задачу:
До вищесказаного можна додати наступне. Далеко не всі пулл-реквести приймаються розробниками. Тут потрібно дотримати ряд правил:
Пулл-реквест (ПР) повинен бути добре оформлений і містити вичерпний опис.
Звичайне правило, один баг - один ПР, одна фіча - один ПР. Не потрібно намагатися запхати відразу купу всього.
Дуже важливо дотримуватися Code Style того проєктe, для якого ви робите ПР. Нехай навіть він здається вам протиприродним (наприклад ви завжди робите відступи у вигляді 4 пробіли, а в проєкті таби).
Не потрібно боятися робити ПР-и, адже допомогти можна навіть в дрібниці. Наприклад ви знайшли помилку перекладу в readme файлі або вам здається що якийсь опис фічі можна зрозумілішо перефразувати.
На гітхабі мільйони проєктів, які живуть виключно на ентузіазмі творців, хороші ПР-и дуже добре стимулюють цей ентузіазм)
Команда:
Приклад:
У Вашому випадку:
Що означає
Різниця між PUT і POST - це питання семантики. Оскільки для операцій використовуються різні дієслова, то і сенс у них повинен бути різним.
Уявіть, що ваш сервіс оперує поняттями блокнот (notebook) і запис (post). Один блокнот може містити безліч записів.
Для додавання нового запису в блокнот c ідентифікатором id ви будете використовувати метод POST з URL mydomain/notebooks/id/. Ваш сервіс, орієнтуючись на метод POST, сам присвоїть потрібний ідентифікатор запису, додасть її в блокнот і поверне вам URL створеного запису (для доступу до запису по GET або для видалення по DELETE). При цьому добре б повернути клієнту URL створеної записи.
Припустимо, запис з ідентифікатором post-id вже створено і він доступний по URL mydomain/notebooks/id/posts/post-id. Але клієнт (власник запису) виправив в ній помилку і хоче перезаписати її. Для цього він використовує метод PUT з URL mydomain/notebooks/id/posts/post-id і передає оновлений запис в тілі запиту. Ваш сервіс, орієнтуючись на метод PUT видаляє старий запис і записує новий, при цьому він доступний за тим же URL.
Звичайно, ніхто не заважає вам завжди використовувати метод POST (наприклад HTML 4 дозволяв використовувати тільки методи GET і POST). Але все ж варто дотримуватися рекомендацій з метою однакового трактування методів усіма розробниками.
Рекомендується використовуватися метод POST для створення підлеглого ресурсу (дочірнього по відношенню до іншого ресурсу; приклад блокнота і записи якраз дуже підходить).
Основна ідея - поліпшення переносимості. Не гарантується, що на різних системах виконуваний файл буде лежати по шляху, який вказаний в shebang.
Використання
env
дозволяє знизити цей ризик за рахунок запуску команди на основі даних зі змінної середовищаPATH
Більш того, якщо з яких-небудь причин замість стандартного файлу користувач хоче використовувати свій, то йому достатньо додати шлях до цього файлу в
PATH
без необхідності виправлення скриптів:В наведеному вище прикладі я скопіював
bash
до себе в домашню директорію (перейменувавши при цьому файл вpython
), додав шлях вPATH
і запустивpython
за допомогоюenv
, яка запустилаbash
, тому що знайшла його раніше.Ще одним прикладом є використання віртуальних оточень при розробці на Python (virtualenv). Оскільки вони також перебивають
PATH
,env
дозволяє використовувати потрібну версію виконуваного файлу:Це можна зробити так:
або так
або так
або так
або так
або так (поки що найкоротший запис)
Виправити помилку можна наступним чином
guzzlehttp/psr7
composer.json
міняємо версію з"guzzlehttp/psr7": "^2.0"
, на"guzzlehttp/psr7": "^1.5"
paquettg/php-html-parser
командоюЯ б рекомендував вибирати серед найпопулярніших дистрибутивів: Ubuntu, Mint, Fedora, Manjaro. Вибирайте яка графічна оболонка вам більше подобається (KDE, Gnome, Mate, Cinnamon, Unity, Pantheon, Xfce) і далі вибирайте з топових дистрибутивів які йдуть з цією оболонкою
Обмеження при створенні статті наступні:
[]{}#%^&()=\|/"~
) та emoji.Знайдіть індекс елемента масиву, який потрібно видалити, за допомогою
indexOf
, а потім видаліть цей індекс за допомогоюsplice
.Другим параметром
splice
є кількість елементів, які потрібно видалити. Зауважте, щоsplice
модифікує масив на місці та повертає новий масив, що містить елементи, які було видалено.Прибрав
expo-router/babel
з файлуbabel.config.js
і все працює.Знайшов рішення цієї проблеми на Reddit
Для цього достатньо сильно подути в отвори біля колеса, це має вирішити проблему.
На скільки я знаю, зараз однією з найкращих відкритих мовних моделей є Mistral
Локально багато мовних моделей можна запустити за допомогою проєку Ollama
Також можу порекомендувати веб інтерфейс Open WebUI через який можна скачувати і запускати різні мовні моделі.
У випадку мовних моделей B означає мільярд, тобто 11B це модель яка містить 11 мільярдів зв'язків (в реальності там трохи складніше). І так, чим більше в моделі параметрів тим більше треба пам'яті щоб запустити модель.
Там можна перший місяць користуватися безкоштовно, принаймні раніше така опція була.
Алгоритмічна рекурсія - це за визначенням алгоритм, побудований зі стратегії Розділяй та володарюй (Divide-and-Conquer), в якому для зберігання підзадач використана LIFO структура даних, тобто, попросту кажучи, стек.
У таких алгоритмів натуральним чином є прямий хід, коли задача розбивається на дрібніші підзадачі, які заносяться в стек. Потім підзадачі витягуються зі стека по одній і вирішуються за таким же принципом, тобто розбиваються на ще дрібніші підзадачі. Розбиття триває до тих пір, поки підзадача не стане розв'язуватися тривіально.
А також у рекурсивних алгоритмів є зворотний хід, коли все дрібніші підзадачі вже вирішені і їх рішення тепер можна об'єднати в рішення більше завдання.
Наявність зворотного ходу (backtracking) - відмінна риса саме рекурсивних алгоритмів. Тобто в рекурсії завжди є зворотний хід. Ось, власне, "при чому тут рекурсія".
Не всім рекурсивним алгоритмам потрібен цей зворотний хід - деяким алгоритмам просто нічого не потрібно робити на зворотному ході. Але сам процес зворотного ходу в рекурсивному алгоритмі завжди присутній, хай навіть і незримо.
Тому якщо ви розглядаєте якийсь рекурсивний алгоритм (перебору або чого-небудь ще), то там завжди обов'язково буде і "повернення" (тобто зворотний хід). А вже як він використовується в вашому алгоритмі та чи використовується взагалі - залежить від алгоритму.
У рекурсивному алгоритмі розставлення
N
ферзів на шахівниці, підзадачею є завдання розставленняm
ферзів що залишилися(m < = N)
, коли першіN - m
ферзів вже якось розставлені. Зворотний хід в цьому алгоритмі використовується тоді, коли ми раптом з'ясували, що підзадача не має рішення - ми повертаємо цей результат на попередній рівень рекурсії в процесі зворотного ходу і тим самим говоримо йому, що треба спробувати якийсь інший варіант розставленняN - m
перших ферзів. А також, якщо вам доручено знайти всі можливі розстановки (а не якусь одну), зворотний хід рекурсії буде використовуватися для тих же цілей незалежно від того, чи успішно вирішена підзадача, чи ні.Підписуйтесь на щотижневу розсилку
Отримуйте найкращі статті тижня на поштуПідписуйтесь на щотижневу розсилку