Rekurzija u C-u

To je pretraga po dubini, DFS.

Karakteristika pretrage po dubini jest da se implementira rekurzivno i da obiđe cijelo stablo pretrage tako da najprije u dubinu istraži jednu granu rekurzije, pa se vrati po sljedeću granu rekurzije. To je čini da nije baš efikasna jer pronađe rješenje na većoj dubini nego što se možda rješenje u drugoj grani pretrage nalazi.

Osnovni pojmovi kod DFS su faktor grananja i dubina pretrage.

                                                                          1

                                                                 2                3

                                                          4            5    6         7

Kod ovog primjera je faktor grananja 2 jer svaka rekurzija poziva dvije rekurzije. Broj 1 se nalazi na prvom nivou pretrage odnosno dubini, a broj 4 na trećem.

Pozivi rekurzija izgledaju ovako:

1

2

4

5

3

6

7

Kod tvog konkretnog koda je grananje rekurzije baš ovakvo, s tim da su određeni prekidni uvjeti koja će se rekurzija prihvatiti a koja odbaciti. Faktor grananja je 4, a dubnina rekurzije 17. Ako imaš VS, opali break point na funkciji, pokreni program sa F5 i sa F 11 korak po korak vidi kako se rekurzija grana na stacku. To možeš vidjeti u prozoru Call Stack, a postoji mogućnost i da u tom prozoru u konteksnom izborniku namjestiš i da vidiš vrijednosti parametara.

Što se tiče ovog zadatka, ja bi rekao da nije dobro riješen. Za 5 lopoča daje preko 1500 rješenja, što znači da je rekurzija obuhvatila kombinacije sa ponavljanjem svih mogućih vrsta i duljine do dubine 17.

Tu bi trebalo staviti memoizaciju rekurzije i uzeti u obzir samo kombijacije bez ponavljanja. To se postiže sa jednim globalnim nizom koji za svaku pojedinačnu kombinaciju pamti gdje smo bili da ne idemo ponovno.

#include<iostream>

using namespace std;

int broj;
int polje[60];

int frog(int n, int position, int step) {
   if (step > 17)
      return 0;
   if (position > n || position < 1 || (step == 0 && position == n))
      return 0;
   if (position == n) {
      return 1;
   }
   if (polje[position] > 0) return 0;
   polje[position] = 1;
   broj = frog(n, position + 2, step + 1)
      + frog(n, position + 3, step + 1)
      + frog(n, position - 2, step + 1)
      + frog(n, position - 3, step + 1);
   polje[position] = 0;
   return broj;
}

int main()
{
   cout << frog(4, 1, 0);
   return 0;
}