Рекурсия и търсене с връщане

Recursion and Backtrack

Какво е рекурсия? Чести проблеми с рекурсията.
Пълно изчерпване. Търсене с връщане

Автор: Александър Георгиев

Макар и вече да знаем какво е итерацията и да ползвахме функции, все още не сме казали почти нищо за една от най-основните техники в програмирането - рекурсията. Тя е основният начин за решаване на голям набор от задачи, като също така е част от редица алгоритми. Тук ще поговорим малко за това, и най-вече как да я ползваме, когато искаме да изпробваме всички възможности в дадена задача.

Рекурсия

За да разберете основната идея на рекурсията, погледнете тази тема.

Идея

Добре де, ще го обясним и с думи. Най-просто казано, рекурсията е функция, която вика себе си. Обикновено, преди да се самоизвика, тя променя някакви данни, или се вика с различни аргументи. В противен случай, тя би продължила да го прави до безкрай, което на теория би накарало програмата ви никога да не завърши, а на практика води до crash. И в двата случая тя не работи, така че лесно ще забележите, ако нещо от този сорт не е наред.

Употреба

Какъв е смисълът да имаме рекурсивно решение? Много често, за да решим дадена задача, ще трябва да решим една или повече подзадачи от същия тип, но с различни аргументи. Явен пример за това са алгоритми, базирани на "разделяй и владей", тъй като, както казахме, там решаваме подзадачи от същия тип. Логично, след разделянето можем да пуснем същата функция да реши и всяка от подзадачите.

Алтернатива на итерацията

Съществуват програмни езици, които нямат итерация в себе си - при тях всичко се извършва чрез викане на функции, като много често се ползва рекурсия. Такива езици се наричат функционални, и, макар и да са много интересни от теоретична гледна точка, не са особено приложими на практика. С някои от тях ще се запознаете в университета.

Хм, но нали казахме, че двоичното търсене е може би най-разпространеният алгоритъм, базиран на "разделяй и владей"? Тогава защо е итеративен?

Всяка рекурсивна програма може да се напише и итеративно. Обратното също е вярно - всяка итеративна програма може да се напише рекурсивно. Като цяло, двата начина на писане са взаимно-заменяеми, като в някои случаи е по-удобно да се ползва единия от тях, докато в други - другия. Ако се замислите, наистина няма проблем да имплементираме двоично търсене и рекурсивно. Всъщност, хайде да го направим! Ще ползваме същата задача, която дадохме за пример и в темата за двоично търсене:

Ели и Станчо играят на следната игра. Станчо си намисля число между 1 и 1000, включително, а Ели се опитва да го отгатне. След всяко нейно предположение, Станчо ѝ казва дали е уцелила, и ако не е - дали неговото число е по-голямо или по-малко ("нагоре" или "надолу"). За всяко питане тя трябва да пие шотче... натурален сок, а след като познае, Станчо трябва да допие останалото в бутилката. Тъй като от натуралния сок на нея ѝ се замайва главата, тя се стреми да познае числото на Станчо с възможно най-малко питания. Помогнете на Ели да измисли стратегия, с която да постигне това.

Имплементацията ще е отново чрез двоично търсене, само че този път рекурсивно.

// Приемаме, че функцията guess(X) връща 0, ако числото на Станчо е X,
// -1, ако неговото е по-малко и +1, ако е по-голямо.
int
 recurse(int
 left,
 int right) {
    if
 (left > right)
        return
 -
1
;
 // Everybody lies.
    int
 mid =
 (left +
 right) /
 2
;
    int
 ansForMid =
 guess(mid);
    if
 (ansForMid =
=
 0)
        return
 mid;
    if
 (ansForMid <
 0)
        return
 recurse(left,
 mid -
 1
);
    return
 recurse(mid +
 1
,
 right);
}

int
 guessStanchosNumber(void) {
    return
 recurse(1
,
 1000
);
}

Двете имплементации са почти напълно еквивалентни, като някои хора предпочитат рекурсивния вариант, а други - итеративния. Повечето състезатели, обаче, ползват итеративния такъв.

Чести проблеми при рекурсия

Тъй като има два особено чести проблема, които се срещат при писане на рекурсия, тук ще обърнем специално внимание на тях, с надеждата да ги избегнете (или поне да ги дебъгнете по-бързо) когато ги срещнете.

Терминиране на рекурсията

Първото и най-важно нещо, за което трябва да внимавате винаги, когато пишете рекурсия, е кога да спрете да я викате. Както всеки цикъл има условия, при които да спира, то и всяка рекурсия трябва да има такива. Това често се нарича "дъно на рекурсията", тъй като, ако си го представите като дупка, в която влизате все по-навътре и по-навътре, то рано или късно трябва да спрете, като това ще е дъното й.

Обикновено условията за терминиране на рекурсията могат да се сложат съвсем в началото на тялото, затова ви съветваме те да са първото нещо, което пишете. В примера с двоичното търсене, условието е същото, което ползвахме и в while() цикъла от итеративния вариант - когато лявата ни граница стане по-голяма от дясната, значи вече интервалът не съдържа нито един елемент и можем да приключим.

Stack Overflow

"Stack overflow", или "препълване на стека", е една от най-честите грешки, които програмистите (не само състезателите) допускат. Не случайно и един от най-големите кодерски форуми се казва StackOverflow. Все още е малко рано да говорим за системния стек (за това ще говорим малко по-късно), но все пак много искахме да го имате предвид. Препълване на стека се получава, когато имаме твърде много данни в тялото на функциите си. А тъй като рекурсията, при самоизвикването си, все едно създава нова функция, то ако сме влезли с дълбочина K навътре, все едно имаме K функции. В случая с двоичното търсене, което написахме преди малко, тази дълбочина би била едва десет, което не е голям проблем. Но в някои случаи ще пишете рекурсии, чиято дълбочина може да стане много голяма.

Максималната дълбочина на рекурсията зависи основно от две неща: колко данни имате в самата функция (включително аргументите й), и колко голям е стекът на програмата. Обикновено, под Windows той е един мегабайт, а под Linux - четири. Това общо-взето значи, че стандартна рекурсия (без много данни, като например тази, която написахме) би била окей до около 20000-40000 нива навътре под Windows и четири пъти по толкова под Linux.

За любознателните ще кажем как с по-голяма точност можете да определите максималната дълбочина на рекурсията. За целта трябва да изчислите приблизително колко байта памет ви отнема всяко нейно ниво. Това става не много сложно, като просто трябва да съберете:

Стекова рамка на функцията, която е или 4 или 8 байта, в зависимост от компилатора и машината. За да сме сигурни, считаме, че е 8.
Ако функцията ни връща нещо - неговия размер. Тоест ако имаме int recurse() трябва да вземем размера на int, което за момента е почти винаги 4 байта; ако връщаме double, трябва да прибавим 8 байта, и т.н.
Ако функцията има аргументи - добавяме към сумата размера на всеки от тях. Указатели и референции са по 4 или 8 (отново, в зависимост дали 32-битов или 64-битов компилатор + машина).
Ако вътре във функцията заделяме някакви променливи (включително променливи, които ползваме в циклите), те също биват прибавени в сумата.

За нашата имплементация по-горе имаме:

8 байта за самата функция;
4 байта за int-а, който връщаме;
8 (4 + 4) байта, за двата int-а, които подаваме като аргументи (left и right);
8 (4 + 4) байта, за двата допълнителни int-a, които ползваме в тялото на рекурсията (mid и ansForMid).

Това прави общо по 28 байта на ниво. Ако сме под Windows, един мегабайт е 1048586 байта, тоест имаме стек за 1048576 / 28 = 37449 нива. Но имайте предвид, че стекът се ползва и за другите функции и малко допълнителни данни, нужни за самата програма, така че този брой всъщност е малко по-малко. Все пак, 30000 нива биха били окей.

Ето сорса на програма, която рекурсивно сумира числата от 1 до N. Можете да пробвате да я пуснете с различни стойности на N, като очакваният отговор трябва да е, разбира се, N * (N + 1) / 2. Забележете, че въпреки, че имаме само 12 байта (8 за функцията + 4 за аргумента) на ниво от рекурсията, то с един милион нива тя крашва.

#include <cstdio>

long
 long
 sum =
 0
;
void
 sum1toN(int N) {
    if
 (N <
 1)
        return
;
    sum1toN(N -
 1
);
    sum +
=
 N;
}

int
 main(void) {
    sum1toN(1000000
);
    fprintf(stdout
,
 "%lld\n"
,
 sum);
    return
 0
;
}

Стек овърфлоу можем лесно да получим и без рекурсия. Примерно вижте следния код, който успешно прави това:

#include <cstdio>
int main() {
    int
 a[2000000
];
    for
 (int
 i =
 0
;
 i <
 2000000
;
 i+
+)
        a[i] =
 i *
 3
 -
 a[i /
 2
];
    for
 (int
 i =
 0
;
 i <
 2000000
;
 i +
=
 123456)
        fprintf(stdout
,
 "%d\n"
,
 a[i]);
    return
 0
;
}

Кое е нещото, което е проблемно в случая?

Опашкова рекурсия

Опашкова рекурсия, или Tail Recursion Optimization (също и Tail Call Optimization), както ще я срещнете по-често, е оптимизация, която компилаторът понякога извършва върху рекурсивен код без да ви казва за това. Ако той счете, че рекурсията е достатъчно проста (от специфичен тип) и може да я превърне в итерация, то той прави това. Така програмата ви става от една страна по-бърза (викането на функция изисква време, колкото и малко да е то), по-ефективна откъм памет (тъй като преизползва едни и същи променливи за различните нива на рекурсията), и по-сигурна (тъй като няма шанс за stack overflow).

Модерните компилатори я извършват, когато рекурсията се вика само веднъж, и то като последна операция в тялото си. Например следният код, макар и почти идентичен с горния, върви без проблем дори за N = 1,000,000,000, тъй като компилаторът го превръща в итеративен такъв:

#include <cstdio>

long
 long
 sum1toN(int N) {
    if
 (N <
 1)
        return
 0
;
    return
 N +
 sum1toN(N -
 1
);
}

int
 main(void) {
    fprintf(stdout
,
 "%lld\n"
,
 sum1toN(1000000000
));
    return
 0
;
}

Пълно изчерпване

Един от най-универсалните начини за решаване на почти всяка задача е като просто проверим всички възможности (разделяния, пътища, нареждания, комбинации, пермутации, каквото и да се търси в задачата), като една от тях ще е отговора, който търсим. Тъй като тук се опитваме да решим проблема по един много праволинеен начин, сходен на отваряне на врата с ритник, този метод се нарича груба сила или bruteforce на английски. Такова решение, в общия случай, рядко би ви донесло много (ако изобщо някакви) точки на състезание, но все пак е от изключителна важност. Първо, все пак има задачи, които могат да се решат за пълен брой точки така. Нещо повече, немалък клас задачи могат да се решат само така (или поне все още не е намерен по-добър начин). В тях ще се иска да имплементирате пълно изчерпване, тоест решение, което изчерпва всички възможности и така намира оптималната (или търсената) стойност. От това какви структури данни ползвате и как точно правите изчерпването ще зависи колко бързо ще върви програмата ви, и съответно колко точки ще получите за задачата.

Търсене с връщане

Може би най-лесният и най-разпространеният начин за писане на пълно изчерпване е чрез рекурсия. Тя позволява много лесно "разклоняване" на търсенето, като така прави кода ни значително по-кратък и интуитивен, отколкото ако ползвахме итеративно изброяване на всички възможности.

?	Пермутация на числата от `1` до `N` е тяхна възможна подредба. Например `(5, 2, 7, 8, 4, 6, 1, 3)` е една от 40320-те пермутации на числата от 1 до 8. Най-малката пермутация е `(1, 2, 3, 4, 5, 6, 7, 8)`, а най-голямата е `(8, 7, 6, 5, 4, 3, 2, 1)`.

Прост пример: пробвайте да напишете две програми, които генерират и изпечатват всички пермутации на числата от 1 до 8 в лексикографски ред, като едната е рекурсивна, а другата - итеративна (без да ползвате next_permutation()). Коя беше по-трудна както за измисляне, така и за имплементиране?

Тъй като рекурсивното търсенето пробва дадено разклонение, след това се връща обратно откъдето е почнало и пробва следващото разклонение, този тип търсене се нарича търсене с връщане, или на английски backtrack.

Примерна задача

Нека разгледаме една примерна задача, която е малко по-сложна от това да изпечатаме всички пермутации:

Ели е записала на лист хартия N цели числа между 1 и 1000, включително, подредени в редица. В началото тя може да зачеркне произволно от тях, като то става "текущо число". След това тя може да направи едно от следните две неща:

Да зачеркне друго, все още незачеркнато число, което дели текущото
Да зачеркне друго, все още незачеркнато число, което се дели на текущото

Тоест ако последно тя е зачеркнала число със стойност A, то тя може да зачеркне друго число B само ако A % B == 0 или B % A == 0. Новото зачеркнато число става "текущо" и играта продължава докато Ели елиминира всички числа. Ако на някоя стъпка тя не може да зачеркне нито едно число, тя губи играта. Помогнете на Ели, като напишете програма, която намира печеливша последователност, или съобщава, че такава не съществува.

Човек и на око може да сметне, че {1, 3, 8} има решение (3, 1, 8), а {2, 3, 4} няма решение. Когато числата са повече, обаче, това изобщо не е толкова лесно. Примерно кое от {42, 13, 17, 1, 3, 30, 10, 2, 6, 34, 2} и {42, 13, 17, 1, 3, 30, 10, 2, 6, 33, 2} има решение и кое няма? А какво е решението?

Оказва се, че {42, 13, 17, 1, 3, 30, 10, 2, 6, 34, 2} има решение (42, 3, 30, 10, 2, 6, 2, 34, 17, 1, 13), докато {42, 13, 17, 1, 3, 30, 10, 2, 6, 33, 2} няма решение.

Ще решим тази задача с пълно изчерпване (макар и да съществува малко по-ефективно решение - вижте по-надолу). Можем лесно да представим числата като масив с N елемента. Ще пазим допълнителен масив с информация кои числа вече сме зачеркнали. Също така ще се нуждаем и от една допълнителна променлива - каква е била стойността (или индекса) на последното зачеркнато число. Остатъкът от решението ще представлява рекурсия, с която ще създаваме различни валидни редици, докато намерим последователност, съдържаща всички числа, или изчерпим всички възможности и заключим, че такава не съществува.

Основното нещо при бектрека е да отбелязваме, че сме ползвали даден елемент в момента, в който го ползваме (без значение дали преди или след като извикаме рекурсията), като го отбелязваме отново като непосетен ако не открием валиден отговор с него . Това е жизнено важно, защото в противен случай не бихме могли да го ползваме в други редици.

#include <cstdio>

const
 int
 MAX =
 64
;

bool
 used[MAX];
int
 answer[MAX],
 seq[MAX],
 n;

bool
 recurse(int
 last,
 int rem) {
    // Ако вече сме ползвали всички числа, значи сме намерили валиден отговор
    if
 (rem =
=
 0)
        return
 true
;
    
    for
 (int
 i =
 0
;
 i <
 n;
 i+
+) {
        // Ако числото на позиция i е незачеркнато и валидно
        if
 (!
used[i] &
&
 (last %
 seq[i] =
=
 0
 |
|
 seq[i] %
 last =
=
 0)) {
            // Отбелязваме числото като зачеркнато
            used[i] =
 true
;
            // Ако намерим валидна редица, запазваме отговора
            // и връщаме нагоре в рекурсията, че сме намерили такава
            if
 (recurse(seq[i],
 rem -
 1)) {
                answer[n -
 rem] =
 seq[i];
 // Или само i, ако искаме пермутация
                return
 true
;
            }
            // В противен случай, отбелязваме числото обратно като незачеркнато
            used[i] =
 false
;
        }
    }
    // Не сме намерили валиден отговор в този клон на рекурсията
    return
 false
;
}

int
 main(void) {
    seq =
 {42
,
 13
,
 17
,
 1
,
 3
,
 30
,
 10
,
 2
,
 6
,
 34
,
 2
};
 n =
 11
;

    // Отбелязваме всички числа като неизползвани
    for
 (int
 i =
 0
;
 i <
 n;
 i+
+)
        used[i] =
 false
;
    
    // Пускаме рекурсията с "текущо число" 1, тъй като реално то
    // ни позволява да отидем в което и да е друго
    if
 (recurse(1
, n)) {
        fprintf(stdout
,
 "Found a sequence: {%d"
,
 answer[0
]);
        for
 (int
 i =
 1
;
 i <
 n;
 i+
+)
            fprintf(stdout
,
 ", %d"
,
 answer[i]);
        fprintf(stdout
,
 "}\n"
);
    }
    else {
        fprintf(stdout
,
 "No such sequence exists.\n"
);
    }
    return
 0
;
}

Бързодействие

Написаната от нас програма би работила за 10-20 числа, но не и повече.

?	Можете ли да се сетите защо тази задача е различна от задачата Tree?

Интересно е, че има примери със само 50 числа, за които тя би вървяла хиляди години за да намери, че няма решение. Не много яко, нали? Това е така, тъй като (ако имаме N числа) на първа стъпка трябва да изберем едно от N, на втора - едно от N-1 (в най-лошия случай), на трета - едно от N-2 и т.н. Това прави N * (N-1) * (N-2) * … * 1 възможности за избиране на последователност, което е O(N!), или експоненциална сложност.

Наистина, понякога нямаме някои от възможните преходи (например ако предишното ни число е било A и има незачеркнато число B, за което е изпълнено, че нито A % B == 0, нито B % A == 0. Това, обаче, не променя много цялата картинка. Да кажем, че от всяко число едва две от останалите се делят на него или го делят (тоест можем да изберем само две от останалите числа за ново "текущо"). Какво означава това? На първа стъпка имаме N избора, на втора имаме 2, на трета имаме 2, и т.н. Това е по-добре, но все пак води до експоненциална сложност - O(N∙2^N-1)). Nicht gut.

Някои такива задачи (включително описаната по-горе) могат да се решат малко по-ефективно с така нареченото Динамично по Битова Маска, което ще разгледаме по-нататък. Но дори с него сложността на решението би била O(2^N∙N²), което все пак е експоненциално.

Подсказки

Като цяло, бързодействието на бектрек решения е ужасно :) Така че един от големите хинтове за такива задачи е това, че входът е много малък (примерно под 25-30, като най-често под 9-10). Разбира се, това, че входът е малък, изобщо не гарантира, че задачата се решава с бектрек - просто е нещо, което трябва да ви накара да се замислите дали все пак не може да стане така.

Тестващи решения

Много често добрите състезатели пишат решение, базирано на бектрек, за да тестват друго свое решение. Тъй като пълното изчерпване е значително по-прост от повечето други алгоритми, то те са относително сигурни в неговата имплементация. Ако отговорите (за малки стойности) между бързото и бавното решение се различават, то едно от тях е грешно, като най-вероятно това е бързото.

Намиране на малки стойности

Понякога добрите състезатели пишат бектрек решение на задача, за която нямат никаква идея как се решава (ако имат време и нямат друга задача за решаване), като търсят зависимост в първите няколко отговора (тези, за които брутфорсът работи достатъчно бързо). Това не винаги дава резултат, но понякога работи. Дори така да успеете да направите една от десет задачи, то това е по-добре от нищо, нали?

Задачи

За най-тривиална рекурсия можете да решите задачата Company. Schedule е дадена с достатъчно малки ограничения да може да бъде решена с bruteforce (макар и да има полиномиално решение). Задачата Product изисква леко оптимизиран бектрек, докато за Sudoku вече ще ви е нужен доста оптимизиран такъв (но пък ще си имате ваша собствена програма, която решава Судоку :)). За повече задачи - секциите Recursion & Backtrack и Bruteforce от подготовката на тренировъчната система към сайта биха ви били полезни.

Докато правите USACO (част от третата тренировъчна сесия) ще имате възможност да се срещнете с още няколко задачи, които се решават с изчерпване (включително умно такова).

За хората, които искат малко по-голям challenge, ето и една по-сложна:

Postal Vans

ACM South Pacific Region -- 2003

Author: Unknown
Tags: Hard, DP, Recurrence
Statement | Archive | Online Judge

Postal Vans. За нея ще ви дадем малък хинт: генерирайте стойностите за N ≤ 10 и търсете зависимост в тях. В оригиналния си вариант N е до 1000, като там ви трябват и дълги числа, но в архива, който сме подготвили, всички тестове са с N ≤ 40, като long long е достатъчен. Забележка: задачата има и други две решения (с различни идеи), които са далеч по-сложни.

Допълнителни материали

За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.

Страницата е посетена 22245 пъти.