PretrazivanjeSaVracanjem/Cifre/_zad0-cifre.txt

   1 Zadatak 0 - rekurzivno resavanje problema
   2 =========================================
   3
   4 Napisati program koji ce na ekran da ispise sve brojeve sa 4 cifre, odnosno
   5 sve od 0000 do 9999.
   6
   7 0000
   8 0001
   9 0002
  10 0003
  11 0004
  12 ...
  13 1000
  14 1001
  15 ...
  16 9998
  17 9999
  18
  19
  20 Problem resavati pretrazivanjem sa vracanjem, a ne direktno sa nekom
  21 petljom od 0 do 9999.
  22
  23
  24 Ideje
  25 -----
  26
  27 Razmotriti kako problem opisati rekurzivno, a ne iterativno sto bi bio
  28 uobicajeni pristup.
  29
  30 Problem nekako treba razbiti na rekurzivne delove. Ovde mozemo gledati
  31 po duzini, tj broju cifara koje treba obraditi.
  32
  33 Na primer za sve jedncifrene brojeve je samo potrebno probati sve mogucnosti 0-9
  34 i svaki put ispisati to resenje.
  35
  36 Za dve cifre je potrebno probati sve mogucnosti za tu drugu poziciju (0-9) i za
  37 svaku od tih mogucnosti probati sve mogucnosti za jednu cifru.
  38
  39 Odnosno za bilo koji broj cifara, treba da isprobavamo jednu koju trenutno
  40 gledamo, i za svaku od tih mogucnosti generisanje svih resenja sa manjim
  41 brojem cifara.
  42
  43 Kod rekurzivnog resavanja problema je uvek neophodno definisati "trivijalne"
  44 izlaze, tj izvrsavanja metoda u kojima nece biti novih rekurzivnih poziva.
  45 Bitno je da se ceo postupak u nekom momentu zavrsi.
  46
  47 Kod ovog resavanja se to tipicno resava tako sto se rekurzivno uvek ide na
  48 jednu stranu (s leva na desno, ili s desna na levo), a trivijalni pozivi su
  49 kad se stigne na kraj niza ili "ispadne" iz njega (skroz desno, tj skroz
  50 levo).
  51
  52 Povratak unazad se desava pri povratku iz rekurzije, a ne eksplicitnim
  53 pozivima.