Една функција, при пресметката на резултатот кој таа треба да го врати, може да се повика самата себеси. Овој процес се нарекува рекурзија. Во повеќето материјали за учење на програмски јазици, се споменува рекурзијата и како таа се применува. Се разбира, во оваа констатација го вклучуваме и курсот за основите на програмскиот јазик C++ на овој сајт, кој има повеќе предавања за функции и начините на нивно користење. Во продолжение, накратко ќе се потсетиме на овој дел, па ќе продолжиме со начините на користење на рекурзија при пишувањето на алгоритми и пронаоѓање решенија.

Рекурзијата е исклучително корисна при решавањето на проблеми кои може да се сведат на решавање на помали проблеми од ист тип. Кај рекурзивните функции, секогаш (ама секогаш!) мора да наведеме услов за завршување на рекурзијата. Во спротивно, функцијата ќе продолжи да се повикува самата себеси до бесконечност - практично, додека не снема меморија или оперативниот систем не ја сруши нашата програма.

Да разгледаме рекурзивна функција за пресметка на факториел. Вредноста на факториел од даден број N, е еднаква на производот на сите природни броеви помали или еднакви на N. Значи, факториел од 5 (се означува 5!) е еднаква на 120, бидејќи 5!=1*2*3*4*5=120. Ако забележувате од самиот проблем, оваа вредност може да се пресмета користејќи ја вредноста на факториелот од претходниот број, бидејќи вредноста на 4!=1*2*3*4, каде имаме производ на сите природни броеви до 4 - па доколку сакаме да пресметаме факториел од 5, само треба да го помножиме резултатот од 4! со 5 (1*2*3*4 * 5). Слично, вредноста на 3!=1*2*3, итн.

int factorial(int N)
{
     if (N <= 1)                                //N==0 || N==1
          return 1;                             //(0!)=1, (1!)=1, po definicija
     
     return N * factorial(N-1);                 //rekurziven povik
}

Забележете како, на почетокот на функцијата, имаме услов за завршување на рекурзијата. Овој услов е всушност вредност која ни е однапред позната, и која немора да ја пресметуваме (на пример, од математиката е познато дека вредноста на факториелот 0!, и на 1!, е еднаква на 1). Ова е исклучително важно, и е најчестата грешка која што се прави при пишувањето на функции кои се повикуваат самите себеси. Значи, не заборавајте да наведете кога функцијата треба да заврши да се повикува. Компјутерот не може да го открие тоа самиот, и истиот ќе продолжи да ја повикува функцијата без запирање.

Доколку сеуште не ви е јасно што е тоа рекурзија, и како функцијата дадена погоре може да го пресмета резултатот кој го бараме од неа, прочитајте ги двете предавања за функции во другиот курс (за основите на програмскиот јазик C++).

Враќање наназад

Веројатно, често постојат ситуации кога нешто не знаете, или ви е потребен некој специфичен податок. Во овие случаи, најчесто го користиме пребарувачот Google за да пронајдеме нешто што ни е потребно. Притоа, Google ќе ни понуди листа од неколку страници кои одговараат на нашите барања. Ние ќе го посетиме првиот сајт и ќе провериме дали постои податокот таму. Доколку не постои, можеби ќе кликнеме на некој линк на таа страница, и ќе отидеме на друго место. Ако не го пронајдеме податокот ниту таму, веројатно ќе се вратиме наназад неколку чекори, се додека не се вратиме кај резултатите кој ни ги понудил Google, па ќе кликнеме на вториот резултат кој ни е понуден. Оваа постапка може да ја повториме повеќе пати, се додека не дојдеме до бараниот резултат. Дури, често, можеби не ни бараме еден конкретен резултат, туку само сакаме да посетиме повеќе сајтови, и да изброиме на колку од нив постои дадениот податок.

Како што веројатно претпоставувате, при решавањето на проблеми, често користиме алгоритми кои го прават токму ова - разгледување на одредена ситуација/опција, па враќање наназад и разгледување на друга ситуација/опција, итн. Алгоритмите кои го користат овој начин за решавање ќе ги нарекуваме алгоритми кои се враќаат наназад (eng. backtracking).

Притоа, еден од класичните проблеми кои може да ги решиме со овој алгоритам е создавањето на сите пермутации од N елементи. Пермутација претставува секој различен распоред на елементите од едно множество, односно на колку начини може да се наредат N различни елементи во листа. На пример, постојат 6 различни начини да се наредат 3 елементи во листа: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]. Значи, една опција е бројот 1 да е прв, 2 втор, а 3 трет; друга опција е бројот 1 да е прв, 3 втор, а 2 трет, итн.

Создавањето на сите овие пермутации можеме да го направиме со помош на алгоритам кој се враќа наназад - и, се разбира, рекурзивна функција. Функцијата најпрвин ќе го стави бројот 1 на прва позиција, и ќе се повика самата себеси со барање за поставување на другите две вредности (2, и 3). Понатаму, ќе ја постави 2ката на втора позиција, и ќе се повика со барање за поставување на преостанатата вредност (3). Тука, постои само еден број, па тоа е бројот кој ќе дојде на крајот (ова е всушност и условот за завршување на рекурзијата – кој, како што кажавме, мора да го имаме). Од кога ја имаме оваа пермутација (1, 2, 3), рекурзивната функција се враќа еден чекор наназад (како кај примерот со пребарувањето на Google), и сега ја пробуваме другата можност за која вредност да се наоѓа на втората позиција (3 наместо 2), итн. Оваа постапка и враќање наназад ќе продолжи додека не ги испробаме сите можности. Тука, важно е да го запаметиме следното - при одредувањето на параметрите со кои ќе ја повикуваме функцијата, потребно е да имаме доволно информации за одредување на целата состојба. Кај примерот со Google, тоа може да е сајтот на кој се наоѓаме, и кои се оние сајтови кои сме ги искористиле за да стигнеме до него. Кај овој пример, со пермутациите, потребно е да знаеме колку броеви имаме на располагање (на пример, дали пресметуваме пермутации од 3 елементи, или од 10), но и кои броеви сеуште не сме ги поставиле, за да не ги користиме истите броеви по повеќе пати.

Конечно, да видиме како изгледа кодот кој го решава овој проблем. Притоа, забележете дека во овој пример, имаме функција за печатење на пермутациите. Зависно од проблемот кој го решаваме, ова може да е функција која го пресметува бројот на пермутации, прави некоја друга операција со нив, го користи распоредот на пермутацијата за пресметка на нешто друго (на пример, дали постои пат така што може да стигнеме од градот со број 1, па до градот со број 2, па до градот со број 3), итн.

//koristi C++11 - http://mendo.mk/Lecture.do?id=26

#include <iostream>
#include <vector>
#include <set>
using namespace std;

void print(vector<int> &permutation)
{
     for (auto value : permutation)
     {
          cout << value << " ";
     }
     
     cout << endl;
}

void create(vector<int> &permutation, set<int> &used, int nextIndex)
{
     int N = permutation.size();
     
     //dali sme gi postavile site elementi?
     if(nextIndex >= permutation.size())
     {
          print(permutation);
          return;
     }
     else
     {
          //isprobaj ja sekoja mozhna vrednost
          //za postavuvanje vo permutation[nextIndex]
          for(int i=1; i <= N; i++)
          {
               if(used.count(i) == 0)
               {
                    //ne sme ja iskoristile taa vrednost, zemi ja sega
                    used.insert(i);
                    permutation[nextIndex] = i;
                    
                    create(permutation, used, nextIndex+1);
                    
                    //od koga ja isprobavme vrednosta, oslobodi ja istata,
                    //bidejki sega, so slednoto izvrshuvanje  na for-ciklusot,
                    //na ovaa pozicija kje stavime neshto drugo
                    used.erase(i);
                    permutation[nextIndex] = -1;
               }
          }
     }
}

int main()
{
     
     set<int> used;
     vector<int> permutation;
     
     //sozdavame niza od 5 elementi,
     //pa kje napravime permutacii od 5 elementi
     permutation.resize(5);
     create(permutation, used, 0);
     return 0;
}

Обидете се подетално да го разгледате кодот, и да сфатите како истиот функционира. Забележете дека, како параметри на функцијата create(), и испраќаме низа со динамичка големина (каде го чуваме тековниот распоред – т.е. која вредност доаѓа на прва позиција, која вредност на втора, итн), но и множество од вредности кои се веќе искористени на претходно разгледаните позиции, како и вредност nextIndex која означува која е следната позиција на која треба да поставиме број (на пример, ако веќе се поставени првите две вредности, nextIndex=2, бидејќи сега треба да поставиме вредност кај permutation[2], односно на третата позиција).

Алгоритмите со враќање наназад делуваат тешко за разбирање на почетокот, но од кога ќе ги разберете и ќе разгледате повеќе примери, тие се едноставни за пишување, но и многу моќни.

Инаку, интересно, во програмскиот јазик C++ веќе постои функција која што може да ни ги создаде сите пермутации. Истата е наречена next_permutation(), а пред да почнеме да ја повикуваме функцијата треба да имаме низа од вредности (на пример, [1, 2, 3]), и елементите во истата да се подредени од најмал кон најголем. Функцијата, при секое нејзино повикување, ќе создаде нова пермутација – и така, се до создавањето на последната. Слично како и претходната програма, следниот код ги печати сите пермутации од 5 елементи.

//koristi C++11 - http://mendo.mk/Lecture.do?id=26

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void print(vector<int> &permutation)
{
     for (auto value : permutation)
     {
          cout << value << " ";
     }
     
     cout << endl;
}

int main()
{
     
     vector<int> permutation = {1, 2, 3, 4, 5};
     
     do
     {
          print(permutation);
     }
     while(next_permutation(permutation.begin(), permutation.end()));
     
     return 0;
}

Притоа, бидејќи често сакаме да ја разгледаме и првата пермутација, користиме do-while циклус, како во примерот погоре. За крај, да наведеме дека пермутациите и факториелот се поврзани меѓусебно. Имено, факториел од даден број N точно го дава бројот на различни пермутации од N елементи. На пример, факториел од 3 е еднакво на 3!=6, и постојат точно 6 пермутации од 3 елементи.

8 кралици на шаховска табла

Еден од поинтересните, но и позначајните проблеми кои може да се решат со помош на алгоритам со враќање наназад е проблемот на поставување на 8 кралици на шаховска табла – односно, на колку различни начини може да се постават 8 кралици, така што никоја од нив да не напаѓа ниту една друга? Притоа, за оние кои не играат шах, шаховска табла е составена од 8 редови и 8 колони, а кралиците може да се движат хоризонтално, вертикално, или дијагонално - и тоа, по еден или повеќе чекори. Во однос на проблемот кој ние ќе го решаваме, јасно е дека треба да напишеме програма која ќе смести 8 кралици на шаховска табла, така што нема да постојат две кралици кои се наоѓаат во ист ред или во иста колона (бидејќи кралиците може да се движат хоризонтално и вертикално), но и не треба да постојат кралици кои се наоѓаат во иста дијагонала.

Најпрвин, како што наведовме во претходните примери, кога пишуваме рекурзивна функција за алгоритам со враќање наназад, потребно е да одредиме услов за завршување на рекурзијата, но и да определиме кои параметри и се доволни на функцијата за одредување на состојбата. За овој проблем, и двете прашања се доста едноставни – условот за запирање на рекурзијата (кога функцијата ќе престане да се повикува себеси) ќе биде кога веќе имаме поставено 8 кралици на шаховската табла. Од друга страна пак, доволни параметри за одредување на состојбата се бројот на поставени кралици и нивните позиции (каде се тие поставени). Користејќи ги овие параметри, ќе бидеме во можност да ги одредиме можните позиции за следните кралици на шаховската табла.

За решавање на овој проблем, потребно е да напишеме и функција која ќе провери дали две кралици (дадени преку нивните позиции на шаховска табла) се напаѓаат меѓусебно. Со други зборови, дали доколку постои кралица на позиција (2, 3), можеме да поставиме дополнителна кралица на, на пример, позиција (5, 7)? И тука, проверките кои треба да ги направиме се јасни. Две кралици се напаѓаат меѓусебно доколку тие се наоѓаат во ист ред, во иста колона, или се во иста дијагонала.

Притоа, потребно е да знаете дека за секоја позиција постојат две дијагонали кои ни се од интерес - онаа која, гледано од горниот ред, се движи налево и онаа која се движи надесно. Забележете дека, ако ги означиме сите позиции на шаховска табла со број за ред и колона (првата позиција, горе-лево, е прв ред и прва колона, па ја означуваме со 1, 1, итн), тогаш е доста едноставно да одредиме дали две кралици се напаѓаат по една од тие две дијагонали. Имено, забележете од сликата дадена подолу, дека доколку две кралици се наоѓаат во иста дијагонала, тогаш или збирот или разликата на редот и колоната на едната кралица ќе биде еднаков на збирот или разликата на редот и колоната на другата кралица. Поконкретно, кралиците ќе имаат ист збир помеѓу редот и колоната доколку ја разгледуваме дијагоналата која, гледано од горниот ред, се движи налево; или иста разлика доколку ја разгледуваме дијагоналата која, гледано од горниот ред, се движи надесно. На пример, првата кралица означена подолу се наоѓа во ред 3 и колона 5, па збирот тука е 3+5=8, а разликата е 3-5=-2. Другата кралица се наоѓа во ред 6 и колона 2, па збирот е 6+2=8, а разликата е 6-2=4. Овие две кралици се напаѓаат дијагонално (имаат ист збир).

Нормално, во продолжение, во целосната програма која го решава проблемот на 8 кралици на шаховска табла, ќе разгледаме и како конкретно изгледа оваа функција за проверка дали две кралици се напаѓаат меѓусебно. Сепак, пред тоа, да размислиме и како да ги чуваме позициите на кралиците, и како да ги разгледуваме можностите за поставување на секоја следна кралица. За чување на позициите на поставените кралици, ќе користиме пар од целобројни вредности pair<int, int>, кои ќе го означуваат редот и колоната на кралицата, соодветно. Од друга страна пак, при поставување на кралиците, за поефикасно извршување на нашата програма, кралиците ќе ги редиме од горе надолу (ова секако нема да влијае на резултатот), и кога ќе поставиме одреден број кралици (на пример, 5), за следната кралица нема да ги испробуваме сите 64-5 слободни позиции на таблата (8*8=64 е вкупниот број на полиња во шаховска табла), туку само 8-те можни позиции во следниот (6-ти) ред од таблата. Причината поради која ова функционира е бидејќи, како што кажавме погоре, кралиците ќе ги поставуваме од горе надолу, и нема потреба да испробуваме позиции кои се наоѓаат во ист ред како некоја од веќе поставените кралици – едноставно, тоа нема да функционира бидејќи две кралици не може да се наоѓаат во ист ред (истите ќе се напаѓаат меѓусебно).

Да ја разгледаме програмата која го решава овој проблем. Забележете дека, иако ги знаеме позициите на поставените кралици, во оваа програма само го пресметуваме бројот на начини на кои може да поставиме 8 кралици на таблата. Овој резултат го чуваме во променливата counter, која ја имаме дефинирано на врвот на програмата.

#include <iostream>
#include <vector>
using namespace std;

int counter = 0;

bool attacks(pair<int, int> queen1, pair<int, int> queen2)
{
     if(queen1.first == queen2.first)
     {
          //napad od ist red
          return true;
     }
     
     if(queen1.second == queen2.second)
     {
          //napad od ista kolona
          return true;
     }
     
     if(queen1.first - queen1.second == queen2.first - queen2.second)
     {
          //napad od dijagonala
          return true;
     }
     
     if(queen1.first + queen1.second == queen2.first + queen2.second)
     {
          //napad od antidijagonala
          return true;
     }
     
     //nema nikakov napad
     return false;
}

void create(vector<pair<int, int> > queens, int current)
{
     if (current > 8)
     {
          //8 kralici se vekje namesteni
          //izbroi go ova kako edno reshenie
          counter++;
          return;
     }
     else
     {
          //postavi ja kralicata vo sledniot red
          int row = current;
          
          //odberi ja kolonata
          for(int column=1; column <= 8; column++)
          {
               pair<int, int> newQueen = make_pair(row, column);
               
               //proveri dali e napadnata od nekoja vekje postavena kralica?
               bool attacked = false;
               for(int i=1; i < current; i++)
               {
                    if (attacks(queens[i], newQueen))
                    {
                         attacked = true;
                    }
               }
               
               if(!attacked)
               {
                    //rekurziven povik za postavuvanje na slednata kralica
                    queens[current] = newQueen;
                    create(queens, current + 1);
               }
          }
     }
}

int main()
{
     
     vector<pair<int, int> > queens;
     queens.resize(9); //kje koristime indeksi od (1-8), za poednostaven kod
     
     create(queens, 1);
     cout << counter << endl;
     return 0;
}

Во оваа програма, како што кажавме претходно, искористивме трик за да не ги разгледуваме сите можни позиции за секоја следна кралица. Поконкретно, пред да почнеме со пишување на нашето решение, забележавме дека не е возможно две кралици да се наоѓаат во ист ред, па овој факт го искористивме за разгледување на многу помал број на позиции за секоја следна кралица (само еден ред, т.е. 8 позиции; наспроти 64). Ова значително го забрза извршувањето на нашата програма.

Всушност, кај многу проблеми кои ќе ги решавате со алгоритми за враќање наназад, треба да внимавате на големината на проблемот. На пример, за стандардна шаховска табла со димензии 8*8, нашиот алгоритам функционира одлично. Но, за поголема табла (на пример, со димензии 1000*1000), нашиот алгоритам ќе биде исклучително бавен. Имено, за толку голема табла, постојат огромен број на начини за поставување на кралиците, и огромен број на позиции кои нашата програма ќе ги разгледува. Имајте го ова во предвид пред да почнете со решавање на одредена задача, и обидете се (макар грубо) да ја анализирате временската сложеност на вашето решение - на пример, доколку имате еден циклус кој се движи од 1 до N, а функцијата се повикува рекурзивно 8 нивоа во длабочина, ќе треба да се анализираат околу N*N*N*N*N*N*N*N=N⁸ состојби.

За крај, да забележиме дека за решавање на проблемот со поставување на 8 кралици на шаховска табла, можевме да искористиме и други елементи за забрзување на програмата. На пример, можевме да имаме податочна структура која ќе паметеше во кои колони веќе има кралица (за да можеме ефикасно да елиминираме позиции, без да ги разгледуваме веќе поставените кралици). Слично, можевме да имаме и две дополнителни податочни структури за секоја од дијагоналите, кои ќе ги паметеа вредностите на збирот и разликата на редовите и колоните на поставените кралици, за да не мора да го проверуваме ниту тоа - и веднаш да знаеме доколку одредена позиција е нападната по дијагонала. Сепак, како што кажавме и претходно, компјутерите се исклучително брзи при решавање на проблеми каде имаме мали вредности (на пример, само 8 кралици, само 20 градови во некоја држава, и слично). Доколку вашиот алгоритам функционира ефикасно, и не постои причина за пишување на побрзо решение, нема никаква потреба да го правите истото.

Дозвола за користење: CC BY-NC 2.5 ©