counting string length using recursion?

[pembed2003]

Hi all,
As an exercise, I am trying to come up with a function to count the
length of a char* string using recursion. I came up with this:

int count_length(ch ar* s){
if(s == 0)
return 0;
else{
s++;
return 1 + count_length(s) ;
}
}

but it doesn't work. There is a core dump / illegal operation. I tried
to fix it by:

int count_length(ch ar* s){
if(s == 0 || !*s)
return 0;
else{
s++;
return 1 + count_length(s) ;
}
}

This seems to fix the problem and return the correct length. I tested
it with:

count_length(0) ;
count_length("1 2345");

My question is: Why is the first version not work? I though the "if(s
== 0)" check will catch the null pointer, no? Can someone explain to
me? Thanks!

[Kai-Uwe Bux]

Re: counting string length using recursion?

pembed2003 wrote:
[snip][color=blue]
> int count_length(ch ar* s){
> if(s == 0)
> return 0;
> else{
> s++;
> return 1 + count_length(s) ;
> }
> }
>
> but it doesn't work. There is a core dump / illegal operation.by:[/color]
[/snip]

The end of a char string is a 0 character. This routine tests for s==0
and will not catch the end of the string indicated by *s == 0. Thus, the
pointer s will keep moving through memory until it hits a region
that your process is not allowed to access. Then the programm crashes.


Best

Kai-Uwe Bux

[Mark A. Gibbs]

Re: counting string length using recursion?

pembed2003 wrote:
[color=blue]
> Hi all,
> As an exercise, I am trying to come up with a function to count the
> length of a char* string using recursion. I came up with this:
>
> int count_length(ch ar* s){
> if(s == 0)
> return 0;
> else{
> s++;
> return 1 + count_length(s) ;
> }
> }
>
> but it doesn't work. There is a core dump / illegal operation. I tried[/color]

yes, because you never stop counting.
[color=blue]
> to fix it by:
>
> int count_length(ch ar* s){
> if(s == 0 || !*s)
> return 0;
> else{
> s++;
> return 1 + count_length(s) ;
> }
> }
>
> This seems to fix the problem and return the correct length. I tested
> it with:[/color]

yup. the test you have about now first checks to make sure that s is not
a null pointer, then checks to make sure that _what s points to_ is not
0, which denotes the end of the string.

for a clearer example, consider this:

if (s == 0) {
//s is null
}

if (*s == char(0)) { // note the cast for clarity
//s points to a null character - the end of a string
}

if you want my opinion, i'd recommend that you don't return 0 as the
length of a null pointer "string". null pointers are problematic (and
have obviously confused you slightly).

perhaps better would be:

int count_length(ch ar* s){
assert(s != 0);

if (*s == '\0')
return 0;
else{
s++;
return 1 + count_length(s) ;
}
}

or if you do not want to assert, then return -1 or something. that is,
of course, unless you want to allow for null pointer "strings".

remember:
char* str = 0; // null pointer

is not the same as:
char* str = ""; // zero-length string

mark

[Petec]

Re: counting string length using recursion?

pembed2003 wrote:[color=blue]
> Hi all,
> As an exercise, I am trying to come up with a function to count the
> length of a char* string using recursion. I came up with this:
>
> int count_length(ch ar* s){
> if(s == 0)
> return 0;
> else{
> s++;
> return 1 + count_length(s) ;
> }
> }
>
> but it doesn't work. There is a core dump / illegal operation. I tried
> to fix it by:
>
> int count_length(ch ar* s){
> if(s == 0 || !*s)
> return 0;
> else{
> s++;
> return 1 + count_length(s) ;
> }
> }
>
> This seems to fix the problem and return the correct length. I tested
> it with:
>
> count_length(0) ;
> count_length("1 2345");
>
> My question is: Why is the first version not work? I though the "if(s
> == 0)" check will catch the null pointer, no? Can someone explain to
> me? Thanks![/color]

Because a null pointer is not the same as a nul character:

int strlen_r(const char* str)
{
return *str ? strlen_r(str + 1) + 1 : 0;
}

- Pete

[Petec]

Re: counting string length using recursion?

Petec wrote:
<snip>[color=blue]
>
> Because a null pointer is not the same as a nul character:
>
> int strlen_r(const char* str)
> {
> return *str ? strlen_r(str + 1) + 1 : 0;
> }
>[/color]

Note that my version treats a null pointer like the standard library strlen
does: it simply dereferences the null pointer. If you want to do some error
handling for that:

int strlen_r(const char* str)
{
if(!str) throw "null pointer in strlen_r()";
return *str ? strlen_r(str + 1) + 1 : 0;
}

Then clients can catch the error:

int main()
{
const char* str = "hello, world!";
try
{
std::printf("\" %s\" length: %d\n", str, strlen_r(s));
std::printf("NU LL length: %d\n", str, strlen_r(0));
}
catch(const char* ex)
{
std::printf("%s \n", ex);
}

return 0;
}

- Pete

[Julie]

Re: counting string length using recursion?

pembed2003 wrote:[color=blue]
>
> Hi all,
> As an exercise, I am trying to come up with a function to count the
> length of a char* string using recursion. I came up with this:
>
> int count_length(ch ar* s){
> if(s == 0)
> return 0;
> else{
> s++;
> return 1 + count_length(s) ;
> }
> }
>
> but it doesn't work. There is a core dump / illegal operation. I tried
> to fix it by:
>
> int count_length(ch ar* s){
> if(s == 0 || !*s)
> return 0;
> else{
> s++;
> return 1 + count_length(s) ;
> }
> }
>
> This seems to fix the problem and return the correct length. I tested
> it with:
>
> count_length(0) ;
> count_length("1 2345");
>
> My question is: Why is the first version not work? I though the "if(s
> == 0)" check will catch the null pointer, no? Can someone explain to
> me? Thanks![/color]

s is a pointer. Incrementing it moves to the next address. It will only be
zero after it wraps past its limit.

You need to test what s is pointing to:

int count_length(ch ar* s){
if(!*s)
return 0;
// ...

Of course, this presumes that a valid (non NULL) string is passed in. If s can
be NULL, then your second version is most appropriate.

As a matter of clarity, it is more appropriate to write:

++s;

as opposed to:

s++;

[pembed2003]

Re: counting string length using recursion?

"Petec" <x@x.x> wrote in message news:<sfqwc.224 95$Tn6.2808@new sread1.news.pas .earthlink.net> ...[color=blue]
> Petec wrote:
> <snip>[color=green]
> >
> > Because a null pointer is not the same as a nul character:
> >
> > int strlen_r(const char* str)
> > {
> > return *str ? strlen_r(str + 1) + 1 : 0;
> > }
> >[/color]
>
> Note that my version treats a null pointer like the standard library strlen
> does: it simply dereferences the null pointer.
>[/color]

Thanks for everyone who answered my question:

A null pointer != A null character

Now another question for Petec:

You said the standard library strlen simply dereferences the null
pointer but won't that cause problem? Because the null pointer can not
be dereferenced right? In fact, I tried your version:

int strlen_r(const char* str)
{
return *str ? strlen_r(str + 1) + 1 : 0;
}

with:

strlen_r(0);

and the program crash. Can you explain?

[Milan Cermak]

Re: counting string length using recursion?

pembed2003 wrote:[color=blue]
> Now another question for Petec:
>
> You said the standard library strlen simply dereferences the null
> pointer but won't that cause problem? Because the null pointer can not
> be dereferenced right?[/color]

Of course. The strlen function will crash the same way as Petec example
you tried. The second Petec example handles this problem and in case of
NULL pointer it throws out an exception.
[color=blue]
> In fact, I tried your version:
>
> int strlen_r(const char* str)
> {
> return *str ? strlen_r(str + 1) + 1 : 0;
> }
>
> with:
>
> strlen_r(0);
>
> and the program crash. Can you explain?[/color]

[Default User]

Re: counting string length using recursion?

Milan Cermak wrote:[color=blue]
>
> pembed2003 wrote:[color=green]
> > Now another question for Petec:
> >
> > You said the standard library strlen simply dereferences the null
> > pointer but won't that cause problem? Because the null pointer can not
> > be dereferenced right?[/color]
>
> Of course. The strlen function will crash the same way as Petec example
> you tried. The second Petec example handles this problem and in case of
> NULL pointer it throws out an exception.[/color]


To be precise, it probably have undefined behavior. That may be crash.
It may not be a crash. Expecting the system to bail out on UB is a
common error. Instead, the program may charge off and do all sorts of
fun things that don't involve crashing at all.




Brian Rodenborn