在用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中使用这样的递归代码,还是应该避免使用它,除非这种情况确实需要递归(例如,递归下降解析器或树结构)
我到目前为止的想法
递归的优点:
缺点:
解决方案:
笔记
我的问题不是专门针对我的示例,而是一个普遍的问题,即是否应该在C中使用递归。
通常,您想对本质上是递归的任务使用递归,例如步行递归数据结构,对递归定义的结构进行序列化或从“平面”输入生成递归结构(例如解析语言)。您不希望将递归应用于可以用迭代表达的任务,例如步行线性数据结构。
递归是一种强大的机制,但是用它代替迭代就像用大锤*击打苍蝇一样。内存效率和堆栈溢出的可能性都是非常重要的考虑因素,但它们仅次于代码的可理解性。即使您通过让编译器为您优化尾调用而消除了在足以进行迭代的情况下应用递归的负面影响,程序的读者也可能会scratch之以鼻,试图先了解您的操作,然后再了解操作的原因。
当您将递归应用于递归任务(树,递归下降解析器,划分和征服处理整个输入的算法,通过回溯进行搜索)时,由于它与手头的任务相匹配,因此代码变得更具可读性。另一方面,当您将递归应用于固有的非递归任务时,您的代码将变得更难以阅读。
*关于递归与迭代的比喻是从Dijkstra的其中一本书的介绍性章节中借用的。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句