堆栈限制和递归函数

Question

C 程序使用递归来查找图的属性。无法处理大图，因为堆栈 space 太小。程序必须重新编码才能使用显式堆栈和循环。

递归函数是否应该首先检查堆栈 space 中的输入 will "fit"？

在 linux 内核中是否有必须用 'explicit' 递归替换递归函数的示例？

Answer 1

Should recursive functions check the input will "fit" in stack space first?

这通常很难。使用不同的编译器或同一编译器的不同版本或使用不同的编译器开关来编译代码时，每次递归调用所需的堆栈内存量可能会有所不同。事实上，函数在不同的调用中可能需要不同数量的堆栈内存，具体取决于其控制流。

所以如果你认为有严重的溢出堆栈的风险，你应该将递归转换为迭代（可能使用显式堆栈）and/or限制recursions/iterations的数量。

Is there an example in the linux kernel where a recursive function had to be replaced with 'explicit' recursion?

是的。一个很好的例子就是实现符号 link 解析的代码。 Prior to Linux 4.2，代码递归如下：

link_path_walk -> nested_symlink -> follow_link -> link_path_walk

link_path_walk是主要的名字解析函数。如果它检测到符号 link，它会调用 nested_symlink，后者可能会递归调用 link_path_walk。为了减轻内核中的堆栈溢出，nested_symlink 执行以下检查：

if (unlikely(current->link_count >= MAX_NESTED_LINKS)) {
    path_put_conditional(path, nd);
    path_put(&nd->path);
    return -ELOOP;
}

每个任务描述符都有一个link_count字段，每次调用nested_symlink时都会增加。如果它超过了一个固定的阈值（MAX_NESTED_LINKS 在 Linux 4.1.51 中是 8），整个操作将因错误而终止。

从Linux4.2开始，将递归代码改为显式堆栈的迭代代码，阈值放宽为40。本文article详细讨论迭代代码

Stack limit and recursive functions