Скок на вярата: „акт на вяра или опит за нещо, чието съществуване или резултат не може да бъде доказано или известно.“ - Google

Когато за първи път се натъкнах на идеята за рекурсия, ме озадачи как една функция може да използва сама себе си, за да се реши. Все още понякога ми бърка в главата, когато се опитвам да реша сложен проблем с помощта на рекурсия. Честно казано, това не е така само при мен. МНОГО хора се борят с рекурсията и често се демотивират. И това е така, защото понякога една рекурсивна функция няма никакъв смисъл, или изглежда, че няма никакъв смисъл, или просто понякога е трудно да се приложи.

Дори и като начинаещ, как ще разберете функция, за която първо трябва да разберете същата функция. За да изчистя това объркване, ще цитирам това, което моят ментор веднъж ми каза,

„За да разрешите проблем с помощта на рекурсия, трябва да вярвате в рекурсията. Трябва да вземете този скок на вярата. И едно нещо, което винаги трябва да имате в ума си, е, че изграждането на вярата изисква време. Прекарайте малко време с него, вашата вяра ще ви води през това.”

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

Правило #1

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

Правило #2

Дефинирайте рекурсивния случай:В този случай функцията продължава да се извиква отново и отново, докато достигне основното условие. С всяка стъпка проблемът става по-малък и по-прост.

Намиране на път с помощта на рекурсия

Първо прочетете изложението на проблема тук.

Нека приемем, че матрицата е nxm.

Преди да преминем към кода, нека разберем проблема тук.

Да предположим, че има само един ред и n на брой колони, отколкото колко пътя ще има, за да се стигне до n-тата колона? Очевидно само 1.

По същия начин, ако има m реда и само една колона, ще има само 1 път.

Ако това е ясно, можем да кажем, че ако по някакъв начин стигна до последната колона или последния ред, това ще се счита за път.

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

int пътища(int n, int m) // дефиниране на функцията

{

ако(n==1 || m==1) // основно условие

връщане 1;

връщане пътища(n,m-1)+пътища(m,n-1); //рекурсивно повикване

}

Всичко, което ме интересуваше, е да стигна до n-та колона за даден ред и m-ти ред за дадена колона и след това да добавя резултата. И след всяка рекурсия стойността се намалява с единица, докато достигне основния случай.

Можете да разгледате целия код, като щракнете върху тук.

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

Честно казано, рекурсията е сравнително лесна тема, когато я научим теоретично и я използваме само за решаване на вековния пример за намиране на факториел. Но докато преминаваме към малко трудни проблеми, изпълнението му става изключително трудно. Въпреки това, практикуването може да направи нещата малко по-лесни за вас.