RekurzijaIteracija.java

//Poglavje o rekurziji in iteraciji
 
public class RekurzijaIteracija {
 
  static public int f(int n) {
     if (n==0) return 1 ;
     else if (n>0)
       return n*f(n-1) ;
     else // error
       return -1 ; // throw new InvalidInputException() ;
  }
 
  static public int f_i(int n) {
      int f=1 ;
      for (int i=2 ; i <= n ; i++)
        f *= i ;
      return f ;
  }
 
  static public void hanoi(char A, char B, char C,int n) {
    if (n>0) {
      hanoi(A,C,B,n-1) ;
      System.out.println("premik iz " + A + " na " + B);
      hanoi(C,B,A,n-1) ;
    }
  }
 
  static public void hanoi0tail(char A, char B, char C,int n) {
    char T ;
    while (n>0) {
      hanoi(A,C,B,n-1) ;
      System.out.println("premik iz " + A + " na " + B);
      T=A ; A = C ; C = T ;  // zamenjamo zeblja A in C
      n=n-1 ;
    }
  }
  static private int a[] ;
  static public void permInit(int max) {
    a = new int[max] ;
    for (int i=0 ; i < a.length  ; i++)
      a[i] = i+1 ;
  }
  static public void writePermutation() {
    for (int i=0 ; i < a.length  ; i++)
       System.out.print(a[i]+", ") ;
    System.out.println();
  }
  static public void permutationsRec(int n0) {
    if (n0==0)
      writePermutation() ;
    else {
      for (int i=0, temp ; i < n0 ; i++) {
        temp = a[i] ;  a[i] =  a[n0-1] ; a[n0-1] = temp ;
        permutationsRec(n0-1) ;
        temp = a[i] ;  a[i] =  a[n0-1] ; a[n0-1] = temp ;
      }
    }
  }
 
  static public void permutationsIter(int n0) {
 
    class StackElement {
      int n,i, address ;
      StackElement() {}
      StackElement(StackElement e) {
        n=e.n ; i=e.i ; address= e.address ;
      }
    }
 
    StackArray s = new StackArray() ;
    StackElement e = new StackElement() ;
    int temp ;
    e.address = 0 ; e.n = n0 ; s.push(new StackElement(e)) ;
    do {
      e = (StackElement) s.top() ; s.pop() ;
      switch (e.address) {
        case 0:
            if (e.n==0)
               writePermutation() ;
            else {
               e.i=0 ;
               temp = a[e.i] ;  a[e.i] =  a[e.n-1] ; a[e.n-1] = temp ;
               e.address = 1 ; s.push(new StackElement(e)) ;
               e.address = 0 ; e.n = e.n - 1 ; s.push(new StackElement(e)) ;
            }
            break ;
       case 1:
           temp = a[e.i] ;  a[e.i] =  a[e.n-1] ; a[e.n-1] = temp ;
           e.i ++ ;
           if (e.i < e.n) { // another loop
             temp = a[e.i] ;  a[e.i] =  a[e.n-1] ; a[e.n-1] = temp ;
             e.address = 1 ; s.push(new StackElement(e)) ;
             e.address = 0 ; e.n = e.n - 1 ; s.push(new StackElement(e)) ;
           }
           break ;
      }
    } while (!s.empty()) ;
}
 
  public static void main(String[] args) {
    // Fakulteta
    System.out.println("10! = "+f(10));
    System.out.println("10! = "+f_i(10));
    // Hanojski stolpi
    System.out.println("\nHanojski stolpi - poteze rekurzivno:");
    hanoi('A','B','C',3) ;
    System.out.println("\nHanojski stolpi - poteze rekurzivno brez repne rekurzije:");
    hanoi('A','B','C',3) ;
    // permutacija
    System.out.println("\nPermutacije 4 elementov rekurzivno");
    permInit(4) ;
    permutationsRec(4) ;
    System.out.println("\nPermutacije 4 elementov iterativno s skladom");
    permInit(4) ;
    permutationsIter(4) ;
 
  }
 
  /*
  // stevilo rekurzivnih klicev naj bo enako recCalls
  class StackElementType {
      ArgumentType args ; // vrednosti argumentov
                          // bodisi za zacetek rekurzivnega klica
                          //  bodisi za povratek iz rekurzivnega klica
      LocalVarsType locals ;// vrednosti lokalnih spremenljivk
                            // za povratek iz rekurzivnega klica
      int address ; // vrednosti med 0 in RecCalls;  naslov za izvajanje ene iteracije:
                    // address = 0 - zacetek izvajanja rekurzivnega klica
                    // i=address > 0 - povratek iz i-tega rekurzivnega klica
  }
 
  public void recursive(ArgumentType args0) {
    LocalVarsType locals0 ;
 
    if (robniPogoj())
      sRobni ;
    else {
       s0 ;
       recursive(args1) ;
       s1 ;
       recursive(args2) ;
       ...
       recursive(argsRecCalls) ;
       sRecCalls ;
      }
  }
 
  public void iterative(ArgumentType args0) {
    LocalVarsType locals0;
    Stack st = new StackArray();
    StackElementType e;
 
    st.makenull();
    e.args = args0; // samo argumenti, lokalne spremenljivke se niso definirane
    st.push(e);
    do {
      e = st.top();
      st.pop();
      args0 = e.args; // pripravi vrednosti
      locals0 = e.locals; // lokalnih spremenljivk
      switch (e.address) {
        case 0:
          if (robniPogoj())
            sRobni;
          else {
            s0;
            // priprava za povratek
            e.address = 1;
            e.args = args0;
            e.locals = locals;
            st.push(e);
            // priprava za zacetek rek. klica
            e.address = 0;
            e.args = args0; // ustrezno za klic
            st.push(e);
          }
          break;
          .
          .
          .
        case i: //  0 < i < reccals
          si;
          // priprava za povratek
          e.address = i + 1;
          e.args = args0;
          e.locals = locals;
          st.push(e);
          // priprava za zacetek rek. klica
          e.address = 0;
          e.args = args0; // ustrezno za klic
          st.push(e);
          break;
          .
          .
        case RecCalls:
          sRecCalls;
      } // switch
    } while (! st.empty()) ;
  } // iterative
 
*/
}