Recursion in programming

Recursion is a very useful programming technique. It can be simply described as calling the function by the same function. It can be understood better by examples rather than by definitions. 

A recursive algorithm must have the following,

1. Base Case (to stop recursive call at some point)
2. Recursive Call

Example:

Finding factorial of a positive integer.

The factorial of a positive integer is multiplication of a series of descending natural numbers.
eg:

4! = 4 x 3 x 2 x 1

In the above example note the following property.

4! = 4 x (3 x 2 x 1)

4! = 4 x 3!

Therefore for any positive integer n,

n! = n x (n-1)!

The above property enables us to use recursion.

If we write a function to find the factorial of a positive integer, let's call it 'factorial(int number)',

then 

factorial(n) = n x factorial(n-1);

This is the recursive call. 

The base case is the factorial of 1. 

factorial(1) = 1;

Following is a program written in C to find factorial using a recursive algorithm.

[code]


#include <stdio.h>

int main()
{

      int number;
      printf("Enter an ineger: ");
      scanf("%d",&number);
      printf("The factorial is %d",factorial(number));

      return 0;

}

int factorial(int number)
{

      if(number == 1)
            return 1;

      return number*factorial(number-1);

}[/code]

C program to find all combinations of user entered characters.

This program uses user entered characters(up to 8 characters) to generate all possible combinations of  these characters using every character entered. If duplicate characters are entered they will be treated as different characters. This can be useful in generating wordlists used in password cracking.
compiling : gcc -o program program.c -lm
[code]#include <stdio.h>
#include <math.h>  // compile the code with -lm to the end since ceil is used
#include <stdlib.h>

int size;

/*functions used*/
int min_num();
int max_num();
int to_int(int array[size]);
int* to_array(int num);
int is_bounded(int num);
int factorial(int num);

int main()
{
    printf("Enter the number of characters: ");
    scanf("%d",&size);
   
    if(size>8)
    {
        printf("Please enter a number less than 10\n");
        return 0;
    }

    char array[size];
    int i;       
    char c;

    printf("Enter characters seperated by space or newline\n");
    for(i=0; i<size; i++)
    {
        scanf("%c",&c);
        while(c==' ' || c=='\n')
        {
            scanf("%c",&c);
        }
        array[i] = c;       
    }   

    printf("There are %d number of possible combinations(combinations will include duplicate characters if you entered any!)\n",factorial(size));
    printf("Press enter to proceed.....\n");
    getchar();
    getchar();
   
    int iter = min_num();
    int max = max_num();

    int* arr;
   
    while(iter<=max)
    {
        if(is_bounded(iter))
        {   
            arr = to_array(iter);
            for(i=0; i<size; i++)
            {
                printf("%c",array[arr[i]-1]);       
            }
            printf("\n");
        }
        iter++;
    }
   
    return 0;
}

/***********************************************************/
/*returns the integer contructed by the given integer array*/
int to_int(int array[size])
{
    int i, ans = 0;
    for(i=0; i<size; i++)
    {
        ans = ans + array[i];
        ans = ans*10;
    }
    return ans/10;
}

/****************************************************************/
/*convert an integer number to an integer array
return a reference to the array*/
int* to_array(int num)
{
    int* array = malloc(sizeof(int)*size);
    double tmp1;
    int tmp2;
    double tmp3;
    int i;
    for(i = size-1; i>=0; i--)   
    {
        tmp1 = num/10.0;
        tmp2 = num/10;
        tmp3 = ceil((10*tmp1 - 10*tmp2));   
        array[i] = tmp3;
        num = num/10;
    }
    return array;
}

/*********************************************************/
/*check whether an integer has distict digits
and each digit is less than the number of digits
return 1 if conditions are met*/
int is_bounded(int num)
{
    int* array = to_array(num);
   
    int i,j;
    for(i = 0; i<size; i++)
    {
        for(j = 0; j<size && i!=j; j++)
        {
            if(array[i] == array[j])
                return 0;
        }
        if(array[i]>size || array[i]==0)
            return 0;
    }
    return 1;

}

/***********************************************************/
/*returns the maximum number that a number with 'size' number of digits
  and with concecutive digits from 1
  eg: if size = 4
      then max_num() returns 4321*/
int max_num()
{
    int i;
    int arr[size];
    int tmp = size;
    for(i = 0; i<size; i++)
    {
        arr[i] = tmp;
        tmp = tmp-1;
    }
    return to_int(arr);
}

/**************************************************************/
/*does the opposite of max_num()*/
int min_num()
{
    int i;
    int arr[size];
    for(i = 0; i<size; i++)
    {
        arr[i] = i+1;
    }
    return to_int(arr);

}

/*****************************************************************/
/*recursively return the factorial of a given number*/
int factorial(int num)
{
    if(num == 1)
        return 1;
    return num*factorial(num-1);

}[/code]

Example:
./program
Enter the number of characters: 3
Enter characters seperated by space or newline
a b c
There are 6 number of possible combinations(combinations will include duplicate characters if you entered any!)
Press enter to proceed.....

abc
acb
bac
bca
cab
cba