Pretvorba rekurzije v iteracijo

Pretvorba iz rekurzije v iteracijo je zaželjena iz razlogov optimizacije izvajanja izvorne kode. Rekurzivna koda je res lažje berljiva, toda zaradi velike požrešnosti je iterativni algoritem veliko hitrejši in manj hardware-sko zahteven.

Repna rekurzija

Repno rekurzijo lahko trivialno spremenimo v iteracijo.

Repna rekurzija je rekurzivni klic, ki se zaključi takoj, ko se zaključi funkcija, ki je klicala rekurzivni klic.

Hanojski stolpi so delni primer repne rekurzije.

public class HanoiRek {
  public static void main (String[] args) {
    hanoi(3, 'A', 'B', 'C');
  }
 
  private static void hanoi (int n, char a, char b, char c) {
    if (n==1)
      System.out.println("Prestavi obroc s palice "+a+" na palico "+c);
    else {
      hanoi(n-1, a, c, b);
      hanoi(1, a, b, c);
      hanoi(n-1, b, a, c);
    }
  }
}

Splošna sprememba iz rekurzije v iteracijo

Shraniti moramo stanje izvajanja, da ga lahko potem rekonstruiramo po rekurzivnem klicu:

Stanje izvajanja obsega:

• lokalne spremenljivke
• parametre
• pomnilniški naslov

Realizacija s skladom

definiramo abstraktni podatkovni tip ADT:

definiramo programsko strukturo preko vmesnika - vmesnik ščiti podatkovno strukturo, da nimamo neposrednega dostopa in lahko dostopamo samo do smiselnih podatkov - s tem se izognemo največjemu številu programerskih napak

Ker uporabljamo vmesnik, se nam tudi ni treba ukvarjati z implementacijo, zato lahko hitreje in učinkovitejše rešujemo probleme na višjem nivoju.

deklariramo:

• makenull()

ustvarimo prazen sklad

• empty()

vrne boolean če je sklad prazen

• top()

vrne vrh sklada

• push(x,sklad)

postavi x na vrh sklada

• pop(sklad)

zbriše vrhnji element sklada

en element sklada (x) mora vsebovati vse kar obsega stanje izvajanja

Splošna shema

V splošni shemi deklariramo kaj bomo dali na sklad: en element sklada

class StackElType {
  ArgsType args;
  locals VarType locals;
  int address; //0..RECCALLS = število rekurzivnih klicev
}

splošna rekurzivna procedura:

public void recursive(ArgsType args0) {
  LocalVarType locals0;
  if ( robniPogoj() ) sRobni;  //robni pogoj - robni stavki
    else { s0;
           recursive(args1);
           s1;
           recursive(args2);
           .
           .
           recursive(argsRECCALLS); 
           sRECCALLS;
         }

adrese nam povedo kam se moramo vrniti iz rekurzivnega klica

iteracija

kako iterativno implementiramo rekurzijo

public void iterative (ArgsType args0) {
  LocalVarType locals0;
  stack st = ...
  stackElType e;
  st.makenull();  //na zacetku je naš sklad prazen
  e.args = args0; //shranimo zacetne parametre v element
  e.aggress = 0;
  st.push(e);     //postavimo 1. element na sklad
  do {
    e = st.top(); st.pop();
    args0 = e.args; //rekonstruiranje stanja izvajanja
    locals0 = e.locals;
    switch(e.address) {
      case 0:
        if (robniPogoj()) sRobni;
        else {
          s0;
 
          //povratek
          e.address=1;
          e.args=args0;
          e.locals= locals0;
          st.push(e);
 
          //rekurzivni klic
          e.address = 0;
          e.args1;
          st.push(e);
      break;
      case i: //0 < i < RECCALLS
          si;
          e.address = it1;
          e.args = args0;
          e.locals = locals0;
          st.push(e);
          e.address=0;
          e.args = args_(i+1);
          st.push(e);
      break;
      case RECCALLS: sRECCALLS;
    } //switch
  while (!st.empty()) 
  } //iterative

Primer razvoja algoritma

Pretvorba iz rekurzije v iteracijo s pomočjo sklada

izpiši vse permutacije n števil

a[i] = i+1

a [1|2|       | n ]
   0,1,2,.....,n-1
   

permutacije [1,2,3]:

123

132

213

231

312

321

n! variant

permutacijo razvijemo tako, da fiksiramo en element in permutiramo vse ostale elemente

rekurzivni algoritem

static public void permRec(int n0) {
  int i;
  //robni primer
  if (n0==0) izpisPermutacije
  else {
  //rekurzija
    for( i=0; i < n; i++ ) {
      //en element fiksiramo
      zamenjaj(i,n0-1)
      permRec(n0-1);
    }
  }
}

Iterativni algoritem

class StackEl {
  int n,i,address;
}
 
static public void permIt(int n0) {
  stack s = ... ;
  stackEl e;
  e.address=0;
  e.n=n0;
  s.push(e);
  do{
    e = s.top();
 
  switch(e.address) {
    case 0:
      if (e.n == 0) izpis
      else {
        e.i = 0;
        zamenjaj(e.i,e.n-1)
 
        //povratek
        e.address = 1;
        s.push(e);
 
        //rekurzivni klic
        e.address = 0;
        e.n = e.n - 1;
        e.push(e);
      }
      break;
    case 1:  //povratek iz rekurzivnega klica
      zamenjaj(e.i,e.n-1);
      e.i++;
      if(e.i < e.n) {
        zamenjaj(e.i,e.n-1)
        e.address=1;
        s.push(e);
        e.address=0;
        e.n=e.n-1;
        s.push(e);
      }
      break;
  } //switch
  } while(!s.empty())
}