Tag Archives: reverse

Recursive C #2

All day today i’ve been thinking how to implement reverse() function from yesterday post using no helper code. Still no result though. Except the realization, that this whole helper is very slow. Let’s make a test: reverse 103 character string 106 times, shall we?

time ./test2

real	0m26.846s
user	0m26.810s
sys	0m0.016s

Wow, that’s a lot. The reason for that is obviously the fact, that we call strlen() each time _rev() is called and strlen() has linear running time, so we are just adding that running time ever _rev() invocation without any gain because string length do not change during reverse() call. Not cool. We can add another constant parameter to carry initial string length:

static void _rev(char s[], int i, const int l) {
	int k = l - 1 - i;
	
	if (i > k) return;

	char c = s[i];
	s[i] = s[k];
	s[k] = c;

	_rev(s, ++i, l);
}

And then:

void reverse(char s[]) {
	_rev(s, 0, strlen(s));
}

Quite simple. Here’s how it performs:

time ./test1

real	0m2.830s
user	0m2.825s
sys	0m0.002s

Fastaaaa! Mind you, that’s recursive solution which has function call overhead (tail recursion, anyone?) and is just an exercise.

So yeah. Optimize-shmoptimize.

Just started the preprocessor chapters. That should be even funnier, because of all the bugs possibilities. Really looking forward to it.

That’s it for today.

Recursive C

Continuing with C. Last chapter i’ve finished is Recursion. There is an exercise which is to implement recursive function for reversing string in place. Here’s my solution:

void reverse(char s[]) {
	static int i;
	int k = strlen(s) - 1 - i;
	
	if (i > k) {
		i = 0;
		return;
	}

	char c = s[i];
	s[i] = s[k];
	s[k] = c;

	i++;	
	reverse(s);
}

Which is a bit… cheating. And that’s due to the fact, that function is not supposed to keep any kind of state. Look at static int i; which i use to keep track of which position is currently exchanging. This is not very good. Is there a better way? If i would be using Scala, i could just create nested function. In C i have to use static function, which is essentially private.

Here is goes:

void reverse(char s[]) {
	_rev(s, 0);
}

static void _rev(char s[], int i) {
	int k = strlen(s) - 1 - i;

	if (i > k) return;

	char c = s[i];
	s[i] = s[k];
	s[k] = c;

	_rev(s, ++i);
}

Funny enough changing ++i in _rev()‘s last line, to i++ will lead to Segfault because recursion never ends. Why not stack overflow? Here is why.

That concludes recursion for now. Source file here: reverse.c.

That’s it for today.