c++ - 如何使用内联和递归？

Question

来自Programming Language Pragmatics, by Scott ，关于内联和递归:

In-line expansion is also not an option in the general case for recursive subroutines. For the occasional case in which a recursive call is possible but unlikely, it may be desirable to generate a true recursive subroutine, but to expand one level of that routine in-line at each call site.

As a simple example, consider a binary tree whose leaves contain character strings. A routine to return the fringe of this tree (the left-to-right concatenation of the values in its leaves) might look like this in C++:

string fringe(bin_tree *t) {
    // assume both children are nil or neither is
    if (t->left == 0) return t->val;
    return fringe(t->left) + fringe(t->right);
}

A compiler can expand this code in-line if it makes each nested invocation a true subroutine call. Since half the nodes in a binary tree are leaves, this expansion will eliminate half the dynamic calls at run time.

If we expand not only the root calls but also (one level of) the two calls within the true subroutine version, only a quarter of the original dynamic calls will remain.

我无法理解以下句子:

• “在每个调用站点内联扩展该例程的一级”
• “如果此代码使每个嵌套调用成为真正的子例程调用，则内联展开此代码。”
• “不仅扩展根调用，还扩展真正子例程版本中的两个调用(一级)”

它们实际上是什么意思？您能否用给定的示例来解释它们，例如，显示执行每个句子的操作后代码是什么样的？

谢谢。

Answer 1

到目前为止，理解这一点的最简单方法是将内联视为创建替代的二进制表示形式。例如。除了创建基本的 string fringe(bin_tree *t) 之外，编译器还可能决定创建 string fringe__inlined(bin_tree *t) 。在 fringe__inlined 中，实际的内联函数将是 fringe 的一个或两个拷贝。

甚至可以通过这种方式创建一个fringe__inlined__inlined(如上所述，有两个级别)。