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
5	3	9	17	2	20	13	1	4	6	7
	lo®	lo						hi	¬ hi	¬ hi
		4						9
		lo®	lo				hi	¬ hi
			1				17
			lo®	lo®	lo
				hi	¬ hi	¬ hi	¬ hi
2				5
2	3	4	1	5	20	13	17	9	6	7

    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)


}