2

I was wondering whether someone could explain how this small code snippet works. 

void reverse(char *s)
{
   if(*s)
       reverse(s+1);
   else
       return;

   cout << *s;
}

When you call this function in main, it supposedly prints out the reverse of any string put in (ie. hello would cout as olleh) but I don't understand how. As I understand it, the if statement increases the value of s until it reaches the end of the string, printing out each value in the string as it goes. Why doesn't that just re-print the string. Clearly I am missing something. (Sorry btw, I am new to C++ and recursive functions)

4

5 回答 5

3

考虑"hello"字符串是如何存储在内存中的：假设其'h'字符的地址恰好是0xC000. 然后字符串的其余部分将按如下方式存储：

0xC000 'h'
0xC001 'e'
0xC002 'l'
0xC003 'l'
0xC004 'o'
0xC005 '\0'

现在考虑一系列调用reverse： 初始调用通过0xC000；来自内部的调用reverse反向传递s+1，因此下一级得到0xC001；下一个得到0xC002，依此类推。

请注意，每个级别都会调用下一个级别，直到看到 的级别'\0'。在我们归零之前，堆栈是这样“加载”的：

reverse(0xC004) // the last invocation before we hit '\0'
reverse(0xC003)
reverse(0xC002)
reverse(0xC001)
reverse(0xC000) // the earliest invocation

现在，当顶部调用调用时reverse(0xC005)，检查*s失败，并且函数立即返回而不打印任何内容。此时堆栈开始“展开”，打印其s参数指向的任何内容：

0xC004 -> prints 'o', then returns to the previous level
0xC003 -> prints 'l', then returns to the previous level
0xC002 -> prints 'l', then returns to the previous level
0xC001 -> prints 'e', then returns to the previous level
0xC000 -> prints 'h', then returns for good.

这就是打印原始"hello"字符串的反向的方式。

于 2013-08-07T16:52:10.843 回答
3

尝试可视化调用堆栈是如何构建的。每个递归调用都会创建另一个堆栈帧，其中的副本s递增 1。当退出条件发生时，堆栈开始展开并cout为每一帧调用语句。由于 LIFO 原理，字符串是反向打印的。

在此处输入图像描述

于 2013-08-07T16:59:16.793 回答
2

让我们考虑一个长度为 3. 的字符串，reverse(i)它是在字符串的第 i 个索引上调用的函数的缩写（从技术上讲，它是 char 指针 + i，但这种解释需要更高级的理解）。

注意（正如罗伯特指出的那样）如果指向，*s则返回 false也很有用，它表示字符串的结尾，因此，在这种情况下，它将简单地返回。s\0

这是发生的事情：

reverse(0)
  calls reverse(1)
    calls reverse(2)
      calls reverse(3)
        end of string - return
      prints 2
    prints 1
  prints 0
于 2013-08-07T16:54:00.333 回答
1

让我们看一个简单的例子，假设 s = "the"

我们会有：

rev(t) -> 递增指针

rev(h)->增量指针

rev(e) -> 递增指针

rev('\0') （这只会返回）

然后我们会回到 rev(e) 的主体，它会打印 e

然后返回 rev(h) 打印 h

然后最后回到 rev(t) 这将打印 t

按照这个顺序，我们将有：eht（“the”相反）

于 2013-08-07T16:51:04.040 回答
0

也许将函数编写为：

void reverse(const char *s)
{
   if(*s)
   {
     reverse(s+1);
     std::cout << *s;
   }
}

即每个非空字符将在调用下一个字符后打印（通过调用反转）

PD：如果您不修改给定的字符串，请使用“const char*”而不是“char*”。

于 2013-08-07T16:58:18.057 回答