Solutions to Questions on recursion

Click here for the questions

1)
int Fibinocci(int n)
{
   if(n==1)
       return 1;
   else
       n+Fibinocci(n-1);
}

2)
void reverse(char*str)
{
   if(*str != '\0')
               reverse(str+1);
}

3)
int Factorial(int n)
{
   if(n==1)
        return 1;
   else
       return(n*Factorial(n-1);
}

4)
void MoveTower(int disk, int source, int dest, int spare):
{
   if(disk == 1)
       printf("Move top disc from %d to %d\n",source,desc);
   else
   {
       MoveTower(disk - 1, source, spare, dest); 
       printf("Move top disc from %d to %d\n",source,desc);            
                   // Step 2
       MoveTower(disk - 1, spare, dest, source);
   }
}

5)
int gcd(int a,int b)
{
   if(b==0)
       return(a);
   else
       return(gcd(b,a(mod)b);
}

6)
arr is an array containing N integers.You can also change the program by keeping characters.k is initially 0.

void permutation(int *arr, int N, int k)
{
   static level = -1;
   level = level+1;
   arr[k] = level;

    if (level == N)
   {
       if(arr!=0)
       for(int i=0; i < N;i++)
         printf("%d",arr[i]);     
   }
   else
     for (int i = 0; i < N; i++)
         if (arr[i] == 0)
             permutation(arr, N, i);
  level = level-1;
  arr[k] = 0;
}   

7)void combinations(char*str,int no)
{
        int temp1=0;
        int i,count,n=1,num,len;
        
   for(i=0;*(str+i)!='\0';i++);
   len=i;
   
   for(i=0;i < len;i++)
                n=2*n;
        temp=(int*)malloc(len*sizeof(int));
        for(i=0;i < len;i++)
                *(temp+i)=0;
        for(num=0;num <= n;num=num+1)
        {
                temp1=num;
                for(i=0;i < len;i++)
                {
                        *(temp+i) = temp1%2;
                        temp1=temp1/2;
                }
                count=0;
                for(i=0;i < len;i++)
                {
                        if(*(temp+i)==1)
                                count++;
                }
                if(count==no)
      { 
      for(i=0;i < len;i++)
             {
                 if(*(temp+i)==1)
                        printf("%c",*(str+i));
             }
          printf("\n");
                        
   
        }
}

8)
Mergesort:a is an array of n intergers,temp is just a temporary array.low is initially 0 and high is n-1.

void mergesort(int *a,int *temp,int low,int hi)
{
   int mid;
   if(hi==low)
   {
       return;
   }
   else
   {
       mid=(low+hi)/2;
       mergesort(a,temp,low,mid);
       printf("1\n");
       mergesort(a,temp,mid+1,hi);
       printf("2\n");
       merge(a,temp,low,mid+1,hi);
    }
}

void merge(int a[],int temp[],int left,int rig,int r)
{
   printf("%d %d %d\n",left,rig,r);
   int i,l,n,k;
   l=rig-1;
   k=left;
   n=r-left+1;
   while(left<=l&&rig<=r)             
   {
        if(a[left]<=a[rig])
            temp[k++]=a[left++];
        else
            temp[k++]=a[rig++];
   }
   while(left<=l)
        temp[k++]=a[left++];
   while(rig<=r)                
        temp[k++]=a[rig++];         
   for(i=0;i < n;i++,r--)                
        a[r]=temp[r];
}

Quicksort:a is an array of n integers.left is initially 0 and right is n-1.

void quick(int *a, int left, int right)
{
   int temp,i,k;
   temp=left;
   if (left>=right)
   {      
       return;
   }
 
   k=(left+right)/2;
   swap(a,left,k);
   for (i=left+1;i<=right;i++)
   {
        if (a[i] < a[left])
        {
            swap(a,++temp,i);
        }
    }

    swap(a,left,temp); //swap a[left] and a[temp]
    quick(a,left,temp-1);
    quick(a,temp+1,right);
}