c - 关于在 C 中使用递归

Question

在用 C 实现词法分析器时，我发现自己在编写递归代码:

// Return a List of Tokens
List Lexer_run(const char* input) {
    if(input[0] == '\0') {
        return new_List();
    } else {
        // ... Find Token and possibly advance in input for a few characters
        return List_add(Lexer_run(nextInput), newToken);
    }

考虑另一个链表实现的例子

List_length(List* this) {
    if(!this) {
        return 0;
    } else {
        return 1 + List_length(this->next);
    }
}

我想知道我是否总是可以在 C 中使用这样的递归代码，或者我是否应该避免它，除非情况如此 确实需要递归(例如递归下降解析器或树结构)

到目前为止我的想法

递归的优点:

• 可读且优雅

缺点:

• 会迅速导致堆栈溢出(在我的计算机中大约有 1'000'000 个调用)
• 与迭代版本相比可能效率低下

解决方案:

• 使用尾调用优化并让编译器将我的递归转换为循环，但我发现尾调用代码的可读性较差。
• 为我的程序增加堆栈大小

注意

我的问题不是专门针对我的示例，而是一个一般性问题，是否应该使用 C 中的递归。

Answer 1

通常，您希望将递归用于本质上递归的任务，例如遍历递归数据结构、序列化递归定义的结构或从“平面”输入生成递归结构(例如解析语言)。您不想将递归应用于可以用迭代表示的任务，例如遍历线性数据结构。

递归是一种强大的机制，但用它代替迭代就像用大锤打苍蝇一样 ^*。内存效率和堆栈溢出的可能性都是非常重要的考虑因素，但相对于代码的可理解性而言，它们是次要的。即使您通过让编译器为您优化尾部调用来消除在迭代就足够的情况下应用递归的负面影响，您的程序的读者也会挠头试图首先理解您做了什么，然后是您为什么这样做。

当您将递归应用于递归任务(树、递归下降解析器、处理整个输入的分而治之算法、回溯搜索)时，您的代码变得更具可读性，因为它与手头的任务相匹配。另一方面，当您将递归应用于本质上非递归的任务时，您的代码会变得更难阅读。

^* 这个关于递归与迭代的比喻是从 Dijkstra 的一本书的介绍章节中借用的。