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.