我如何判断一个函数是否是尾递归 C？

Question

我这里的函数是尾递归吗？如果是这样，为什么/为什么不呢？我在理解这个概念时遇到了一些困难，因此非常感谢您的帮助。

struct link 
{
  int value; //data    
  link_t *next; //link
};

struct list
{
    link_t *first;
    link_t *last;
};


int list_size_count(link_t *first, int acc)
{
  if (first != NULL)
  {
    return (acc + list_size_count((first->next), 1));
  }
  return acc;
}

int linked_list_size(list_t *list)
{
  return list_size_count((list->first),0);
}

Answer 1

对于尾递归的函数，递归调用必须是它的最后一个动作。在您的代码中，该函数所做的最后一件事是添加两个值，因此 list_size_count() 不是尾递归。

int list_size_count(link_t *first, int acc)
{
  if (first != NULL)
  {
    return (acc + list_size_count((first->next), 1));
  }
  return acc;
}

以下是如何使其成为尾递归：

int list_size_count(link_t *first, int acc)
{
  if(first != NULL)
  {
    return list_size_count(first->next, acc + 1);
  }

  return acc;
}

Answer 2

Is my function here a tail recursion?

不，不是。

这一行

return (acc + list_size_count((first->next), 1));

在递归调用 return 之后包含一个加法操作 ，即 acc 的加法以及任何递归调用 returns .因此它不是尾递归。

但是转成尾递归很容易。只需将上面的行更改为：

++acc; return list_size_count((first->next), acc);

这里acc首先递增并作为参数传递给递归函数，递归调用的结果直接在return语句中使用。

现在递归调用后没有任何操作。因此它是尾递归。

Answer 3

如果一个例程的最后一个动作是调用另一个例程，它被称为尾调用。一个例子是一个例程，比如说一个名为 g 的例程，它以 return f(x); 结尾。编译此代码的直接方法是：

传递参数x复制到指定位置传递参数
执行子程序调用指令调用f.
清理堆栈帧（通过将堆栈指针恢复到该例程开始执行时的值）并执行 return 指令。

因为这是例程 g 要做的最后一件事，我们不需要 f 到 return 到 g。我们可以跳转到它，而不是调用它：

将x复制到传递参数的位置。
执行分支指令跳转到f.

然后f会执行，清理我们当前所在的栈帧，执行一条return指令。这会将 return 传递给 g 的调用者，就好像 g 执行了 return 指令一样。我们从这些指令中获得与早期指令相同的效果，但工作量更少。

（此处未显示更多详细信息。为此，管理堆栈帧的规则必须允许 f 清理 g 的堆栈帧，即使 f 也可以在堆栈上建立自己的上下文。)

如果f和g是同一个套路，这就叫尾递归.

请注意，在此示例中，f 和 g 必须 return 相同类型的数据。如果 f return 是一个 float 并且 g return 是一个 int，那么，当 g 包含 return f(x); ，调用 f 实际上并不是 g 所做的最后一件事。 return 语句中有一个从 float 到 int 的自动转换，所以这不会是尾调用。

尾调用必须是例程的最后一个动作；它不必是例程中的最后一个源代码。如果 return f(x); 出现在例程中的任何地方（并且类型匹配），那就是尾调用，它可以被分支替换（如果堆栈管理规则允许）。另外，如果g的return类型是void，那么例程中任何地方的f(x); return;都是尾调用，例程结束的f(x);是尾调用.

在你的例程linked_list_size中，return list_size_count((list->first),0);是尾调用，但不是尾递归

在您的例程 list_size_count 中，没有尾调用，因为在 return (acc + list_size_count((first->next), 1)); 中，+ 在调用 list_size_count 之后执行。您可以通过将其重写为：

使其成为尾调用和尾递归

return list_size_count(first->next, acc+1);

我如何判断一个函数是否是尾递归 C？

How do I tell if a function is tail recursive C?

c

recursion

tail-recursion

linked-list

tail