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 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)

}```