C Program to find all permutations of string by Recursion and Iteration

Recursion : :

• Recursion is the process of repeating items in a self-similar way. In programming languages, if a program allows you to call a function inside the same function, then it is called a recursive call of the function.

• The C programming language supports recursion, i.e., a function to call itself. But while using recursion, programmers need to be careful to define an exit condition from the function, otherwise it will go into an infinite loop.

• Recursive functions are very useful to solve many mathematical problems, such as calculating the factorial of a number, generating Fibonacci series, etc.

Iteration : :

• Iteration, in the context of computer programming, is a process wherein a set of instructions or structures are repeated in a sequence a specified number of times or until a condition is met.

• When the first set of instructions is executed again, it is called an iteration. When a sequence of instructions is executed in a repeated manner, it is called a loop.

Example : :

for (int i=0;i<n;i++)
{
\\ statements;
}

Below is the source code for C Program to find all permutations of string by Recursion and Iteration which is successfully compiled and run on Windows System to produce desired output as shown below :

SOURCE CODE : :

/* C Program to find all permutations of string by Recursion and Iteration */


#include<stdio.h>
#include<string.h>

void Permute1(char str[], char* currentptr);
void Permute2(char str[], int startIndex, int lastIndex);
void Swap(char *a, char *b);

int main()
{
        char str[20];
        printf("Enter any String :: ");
        scanf("%s",str);
        printf("\nUsing Iteration :: \n\n");
        Permute1(str,str);
        printf("\n\n");
        printf("\nUsing Recursion :: \n\n");
        Permute2(str,0,strlen(str)-1);

        printf("\n");

        return 0;
}

//--------------Iteration---------------------

void Permute1(char str[], char* currentptr)
{
        char *ptr;
        if( *(currentptr + 1) == '\0')
           printf("%s\t", str);
        else
        for(ptr=currentptr; *ptr!='\0'; ptr++)
    {
                Swap(ptr,currentptr);
                Permute1(str, currentptr+1);
                Swap(ptr,currentptr);
        }
}

//--------------Recursion---------------------

void Permute2(char str[], int startIndex, int lastIndex)
{
        int i;
        if(startIndex==lastIndex)
        {
                for(i=0;i<=lastIndex;i++)
                        printf("%c",str[i]);
                printf("\t");
        }
        else
        for(i=startIndex;i<=lastIndex;i++)
        {
                Swap(&str[startIndex], &str[i]);
                Permute2(str,startIndex+1,lastIndex);
                Swap(&str[startIndex], &str[i]);
        }
}


void Swap(char *a, char *b)
{
        char temp = *a;  *a=*b; *b=temp;
}

OUTPUT  : :

****************** OUTPUT *********************


****************** FIRST RUN ******************

Enter any String :: xyz

Using Iteration ::

xyz     xzy     yxz     yzx     zyx     zxy


Using Recursion ::

xyz     xzy     yxz     yzx     zyx     zxy



****************** SECOND RUN ******************

Enter any String :: abcd

Using Iteration ::

abcd    abdc    acbd    acdb    adcb    adbc    bacd    badc    bcad    bcda 
bdca    bdac    cbad    cbda    cabd    cadb    cdab    cdba    dbca    dbac 
dcba    dcab    dacb    dabc


Using Recursion ::

abcd    abdc    acbd    acdb    adcb    adbc    bacd    badc    bcad    bcda 
bdca    bdac    cbad    cbda    cabd    cadb    cdab    cdba    dbca    dbac 
dcba    dcab    dacb    dabc