K&Rを読もう(44) 演習 4-13 reverseを再帰で

reverseを再帰で。という難解な設問。僕のScheme力が試される。

いっこめ

strlenで。

void reverse_iter(char *s1, char *s2)
{
    if (*s1 != '\0') {
        *s2 = *s1;
        reverse_iter(s1 + 1, s2 - 1);
    }
}

void reverse(char *s1, char *s2)
{
    int len = strlen(s1);
    *(s2 + len) = '\0';
    reverse_iter(s1, s2 + len - 1);
}

無難だ。

にこめ

文字の長さががわかるなら、半分まで見れば出来るはず。

void reverse_iter2(char *s1, char *s2, int center)
{
    if (center != 0) {
        char tmp = *s2; /* swap */
        *s2 = *s1;
        *s1 = tmp;

        reverse_iter2(s1 + 1, s2 - 1, center - 1);
    }
}

void reverse2(char *s)
{
    int len = strlen(s);

    reverse_iter2(s, s + len - 1, len / 2);
}

swapみたいな。引数いっこ。

さんこめ

strlenは使いたくない。

int reverse_iter3(char s1[], char s2[], int i)
{
    if (s1[i] == '\0') {
        s2[i] = '\0';
        return i - 1;
    } else {
        int tail = reverse_iter3(s1, s2, i + 1);
        s2[tail - i] = s1[i];
        return tail;
    }
}

void reverse3(char s1[], char s2[])
{
    reverse_iter3(s1, s2, 0);
}

自前でstrlenしてるだけだったり。

よんこめ

ポインタポインタで書いてみた。

void reverse_iter4(char *s1, char **s2)
{
    if (*s1 != '\0') {
        reverse_iter4(s1 + 1, s2);
        *(*s2)++ = *s1;
    }
}

void reverse4(char *s1, char *s2)
{
    reverse_iter4(s1, &s2);
    *s2 = '\0';
}

うまくかけた。

ごこめ

ポインタポインタの引数いっこ版

void reverse_iter5(char *s1, char **s2)
{
    if (*s1 != '\0') {
        reverse_iter5(s1 + 1, s2);
        if (s1 > *s2) {
            char tmp = *s1;
            *s1 = **s2;
            *(*s2)++ = tmp;
        }
    }
}

void reverse5(char *s)
{
    reverse_iter5(s, &s);
}

再帰で末尾まで行って、半分までやったら終わり。脱出したい気分。

まとめ

ポインタポインタがお気に入り。