Preferable construction of a function comparing linked lists

[Edwin Galloway]

Is one of the following preferable over the other?

// This function compares two strings(which are linked lists of chars)
// according to their lexicographic order.
// We define ordering as follows:
// c1c2...ck < d1d2...dm if either of the following holds:
// 
// 1) k < m and for i = 1,2,3...k we have ci = di
// 	as a special case k=0 for an empty string e. We say e < s for any nonempty
// 	string s.
//
// 2) for i > 0, the first i-1 characters of two strings agree, but the ith char of the
// 	1st string < ith of the second:
// 	cj = dj, for j = 1,2,3...i-1 and ci < di.

BOOLEAN ProperPrefix(STRING s1, STRING s2){
	if( s1->element == s2->element ){
		ProperPrefix(s1->next, s2->next);
	} else if ( s1->element < s2->element ) {
		return TRUE;
	} else
		return FALSE;

}

My main interest is in the usefulness/necessity of the first "if" in the below version - it seems unnecessary, since iirc NULL is equivalent to 0 when comparing ints.

Other pointers on idiomatic C are welcome.

BOOLEAN is_proper_prefix_string(STRING s1, STRING s2){
	if(s1->element == NULL)
	{
		if(s2->element != NULL) return TRUE;
		else return FALSE;
	}
	else if(s1->element == s2->element)
	{
		is_proper_prefix_string(s1->next, s2->next);
	}
	else if(s1-> element < s2->element)
		return TRUE;
	else
		return FALSE;
}

[Cubbi]

if this is C, then comparing to NULL is wrong in any case; it can be a pointer. (null character value is usually written as '\0'), and you're right, it is not necessary here to check for equality with it, since '\0' compares less than any non-null ASCII character with the less-than operator already (but this is necessary if you're handling single-byte non-ASCII encodings and char might be negative)

Also, watch out for your stack depth: idiomatic C would use a loop.

Also, you're missing a return statement in one of the branches, for a function that's declared to return a value.

[Edwin Galloway]

Cubbi: Thank you for the quick and clear response. Regarding your last point, could you be more specific?

If i understand correctly, the last two suggestions should be taken as one: The recursive branch isn't idiomatic because it doesn't have a way to guard against a stack overflow and also because the recursive branch lacks an explicit return value.

Is that right?

[Cubbi]

well, you could make the recursive branch compile cleanly if you wrote
return ProperPrefix(s1->next, s2->next);
and that would actually guard you from stack overflow on most compilers due to tail call optimization (that return is compiled into an unconditional jmp CPU instruction).. but it's not guaranteed, and a loop is not much more complicated.