strings and recursion

Strings and Recursion

A string can be defined recursively as-

• A string may be an empty string
• A string may be a character followed by a smaller string(one character less).

Now we will write some recursive functions for operations on strings. The first one is to find the length of a string.

The length of empty string is 0 and this will be our terminating condition. In general case, the function is recursively called for a smaller string, which does not contain the first character of the string.

int length(char *str)
{
    if(*str == '\0')
        return 0;
    return(1 + length(str+1));
}

We can print a string by printing the first character of the string followed by printing of the smaller string, if the string is empty there is nothing to be printed so we will do nothing and return(base case).

void display(char *str)
{
    if(*str == '\0')
        return;
    putchar(*str);
    display(str+1);
}

Note that to displaying string in standard order we have placed the printing statement before the recursive call while during the display of numbers from 1 to n, we had placed the printing statement after the recursive call.

By changing the order of printing statement and recursive call we can get the function for displaying string in reverse order.

void revdisplay(char *str)
{
    if(*str == '\0')
        return;
    revdisplay(str+1);
    putchar(*str);
}

We hope that you can understand the reason for this and if not then trace and find out.