Daily Archives: January 27, 2014

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.