Tag Archives: recursion

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.