Recursion to find length of a string in C

Question

I am trying to find the length of a string by recursion using the following code:

#include <stdio.h>
int string_length(char *s, int x);

int main(void)
{
    int length = 0, x;
    char string[] = "This is a string";

    x = string_length(string, length); 
    printf("The length of the string will be: %d\n", x);
    return (0);
}

int string_length(char *c, int x)
{
    int a = 0;
    if (*c != '\0')
    {
        a = a + 1;
        string_length(c + 1, x + 1);
    }
    return (a);
}

But as I run my code, I get the following output:

The length of the string will be: 1

As it can be seen, this is not the correct length. I know that the length of a string is 16. Where did I go wrong.

I have searched for a while, and I have a hint it it has something to do with how I implemented my recursive function. How can I get around my issue?

Answer 1

For starters this function declaration

int string_length(char *s, int x);

does not make a great sense. The second parameter is redundant. Strings have the sentinel value '\0' that forms the basic case of the recursion.

The function always returns either 0 (for an empty string) or 1 because it returns the local variable a

int string_length(char *c, int x)
{
    int a = 0;
    if (*c != '\0')
    {
        a = a + 1;
        string_length(c + 1, x + 1);
    }
    return (a);
}

that does not depend on the recursive call

string_length(c + 1, x + 1);

The function can be defined the following way

size_t string_length( const char *s )
{
    return *s ? 1 + string_length( s + 1 ) : 0;
}

Pay attention to that the type int can be not large enough to be able to store the length of a string. You need to use the type size_t. It is the return type of the standard string function strlen. See the function declaration

size_t strlen(const char *s);

Also as the passed string is not changed within the function then the function parameter should be declared with the qualifier const.

In main you could write

size_t n = string_length( string ); 
printf("The length of the string will be: %zu\n", n);

Here is a demonstration program.

#include <stdio.h>

size_t string_length( const char *s )
{
    return *s ? 1 + string_length( s + 1 ) : 0;
}

int main(void) 
{
    const char *s = "Hello World!";

    printf( "The length of the string \"%s\" is %zu\n", 
            s, string_length( s ) );
}

The program output is

The length of the string "Hello World!" is 12

Answer 2

The problem is a is not a global variable.

What this means: for every depth of your recursion, a new variable a is being created, ignored, then set to 1 and returned. As a is a local variable, int a is separate across depths of your recursion.

---

There are two ways you can go about fixing this.

1. Make a a global variable. Your code could look something like this:

#include <stdio.h>
int string_length(char *s, int x);

int a = 0;
int main(void)
{
    int length = 0, x;
    char string[] = "This is a string";

    x = string_length(string, length); 
    printf("The length of the string will be: %d\n", x);
    return (0);
}

int string_length(char *c, int x)
{
    if (*c != '\0')
    {
        a = a + 1;
        string_length(c + 1, x + 1);
    }
    return (a);
}

Notice, all I did was move int a = 0 above int main(void). As a is now a global variable, its value is preserved between different calls of your recursive function, meaning they are all doing a = a + 1 on the same global variable a.

2. Utilize x.

I've noticed that in your function, you keep track of int x, yet never use it. int x is tracking the depth of your recursion, and you can use this to return the string length.

Your code could look something like this:

#include <stdio.h>
int string_length(char *s, int x);

int main(void)
{
    int length = 0, x;
    char string[] = "This is a string";

    x = string_length(string, length); 
    printf("The length of the string will be: %d\n", x);
    return (0);
}

int string_length(char *c, int x)
{
    if (*c != '\0') 
    {
        return string_length(c + 1, x + 1);
    } else 
    {
        return x;
    }
}

Notice, method 2 (the method shown directly above) is mostly always preferred. This is because declaring lots of variables globally can pollute the global namespace, which is not recommended an leads to unnecessarily messy code.