用C递归

Question

我有下面的代码以递归方式反转字符串,它在递归完成后打印字符时起作用,但我无法弄清楚如何将反向字符组合成字符串并将它们反转给调用者.有人有想法吗？我不想添加另一个参数来累积字符,就这样,这不是功课,我正在研究小事情,因为我将在一年内毕业并且需要在面试时做得好.

char* reversestring5(char* s)
{

    int i = 0;
    //Not at null terminator
    if(*s!=0)
    {

        //advance the pointer
        reversestring5(s+1);
        printf("%c\n",*s);
    }

}

Answer 1

使用递归函数,通常最容易弄清楚如何解决一个简单的情况(例如,用一对字符反转一个字符串),然后看看如何将问题分解成简单的操作,最终导致琐碎的情况.例如,人们可能会这样做:

这是实际的递归函数:

char *revrecurse(char *front, char *back)
{
    if (front < back) {
        char temp = *front;
        *front = *back;
        *back = temp;
        revrecurse(front+1, back-1);
    }
    return front;
}

这部分只使用递归函数:

char *reverse(char *str)
{
    return revrecurse(str, &str[strlen(str)-1]);
}

请注意,这假定指针有效并且指向NUL终止字符串.

如果您要实际反转字符,您可以提供一对指针并递归交换字母(这是此例程所做的)或将字符一次一个地复制到另一个空格中.这基本上就是你的原始代码所做的事情; 复制每个字符的时间stdout是一个未明确传递但正由例程使用的全局结构.该方法的模拟,但使用指针可能如下所示:

#define MAXSTRINGLEN 200

char revbuf[MAXSTRINGLEN];
char *refptr = revbuf;

char *revstring(char *s)
{
    if (*s != 0)
    {
        revstring(s+1);
        *refptr++ = *s;    /* copy non-NUL characters */
    } else {
        *refptr++ = '\0';  /* copy NUL character */
    }
    return revbuf;
}

在对原始代码的这种微小修改中,您现在可以看到此方法对全局变量的依赖revbuf以及refptr隐藏stdout在原始代码中的内容.显然,这甚至没有接近优化 - 它仅用于解释目的.