Sunday, 3 November 2013

RECURSIVE FUNCTIONS

Some calculations have recursive character: for example N!=N*(N-1)!. To be able implement this kind of functions we write functions that call themselves, which are called recursive functions.
Example: Quick Sort is an algorithm for sorting numbers in a recursive way.

elem           
53917220131467 
 lo®lo     hi¬ hi¬ hi 
  4     9   
  lo®lo   hi¬ hi   
   1   17    
   lo®lo®lo      
    hi¬ hi¬ hi¬ hi    
2   5       
23415201317967 
            


    Template <classType>  
    void qsort(Type *ia, int low, int high)
    {//quick sort
       if (low<high) {
       int lo=low+1;
       int hi=high;
       Type elem=*(ia+ low)// check what happens  if  ia [low] is used instead
         while (True)
             {
                while (ia[lo] <elem) {lo++};
                while (ia[ hi] >elem) {hi--};
          if (lo<hi)  swap(ia,lo,hi);
          else break;
    }

    swap(ia,low,hi);
    qsort(ia,low,hi-1);
    qsort(ia, hi+1,high);
    }
  }

Quicksort makes use of a helping function swap (). This, too, needs to be defined as a template function:
    template <class Type>
    static void swap (Type *ia, int i, int j)
    {// swap two elements of an array

    //for the compilers that do not take the size automatically then write explicitly.
    //tmp=*(ia+i*sizeof(Type))
       Type tmp=*(ia+i)
       *(ia+i)= *(ia+j)
        *(ia+j)=tmp
    }
    #include "qsort.c"
    main () {
       int *pA=&A[0]  //or *pA=A check with the compiler
       int *pB=&B[0]
       int     A[] ={5,3,9,17,18,20,13,2,4,6,7}
       double  B[]={12.8,76.0,87.7,98.6, 65.7}
qsort(pA,0,10)
qsort(pB,0,4)
}