如何将基于while循环的Lisp表达式AST构建函数改写为合理的递归实现？

你当前写的所谓递归版本，本质是用尾递归模拟循环逻辑——只是把原有while循环里“找最内层括号、替换切片、更新tokens”的步骤，换成了把替换后的完整token列表传给下一次函数自调用。递归过程没有真正参与嵌套结构的拆解，自然会觉得“递归没有发挥作用”。

你现有的循环/伪递归实现存在两个明显不足：

• 每次匹配左右括号都要全量扫描token列表，每次替换还要做列表切片拷贝，整体时间复杂度为O(n²)，处理深层嵌套表达式时开销很高
• 实现逻辑和Lisp本身的嵌套结构完全割裂：靠“逐次替换最内层括号对”的列表处理技巧模拟解析过程，没有和“左括号进入下一层、右括号返回上一层”的语法结构形成对应

更优雅的递归实现：游标式递归下降解析 #

递归处理嵌套结构的核心，是让函数调用的层级和AST的嵌套层级一一对应：遇到左括号就下沉一层处理子表达式，遇到右括号就上浮一层返回结果。全程只需要一个单向推进的游标，记录当前解析到token列表的位置，不需要反复扫描、切片列表：

• 碰到左括号(：游标前移一位，递归调用当前解析函数，收集这层括号内的所有子表达式，直到碰到匹配的右括号
• 碰到右括号)：游标前移一位，把当前层收集的结果返回给上一层调用方
• 碰到普通token（运算符、数字等）：游标前移一位，把token直接加入当前层的结果列表

可直接运行的实现代码如下：

LEFT_PAREN, RIGHT_PAREN = '(', ')'

def build_ast(tokens):
    pos = 0  # 解析游标，全程单向推进不回溯
    
    def parse_layer():
        nonlocal pos
        current_layer = []
        while pos < len(tokens):
            token = tokens[pos]
            pos += 1
            if token == LEFT_PAREN:
                # 左括号触发递归，解析后续子表达式直到匹配的右括号
                sub_node = parse_layer()
                current_layer.append(sub_node)
            elif token == RIGHT_PAREN:
                # 右括号代表当前层解析结束，返回结果给上一层
                return current_layer
            else:
                current_layer.append(token)
        # 适配最外层无右括号的收尾场景
        return current_layer
    
    return parse_layer()

用原有测试用例验证：输入['(', '+', '2', '(', '*', '3', '4', ')', ')']，输出与你原有实现完全一致：[['+', '2', ['*', '3', '4']]]。

实现的核心优势 #

• 递归逻辑完全贴合Lisp语法结构：嵌套多少层括号，就对应多少层函数调用，没有冗余的模拟步骤
• 时间复杂度为O(n)：每个token只会被游标访问一次，没有重复扫描、列表拷贝的额外开销
• 扩展性极强：后续要支持单引号、注释、宏规则等扩展语法时，只需要在parse_layer的分支判断中增加对应逻辑即可，不需要改动整体解析框架

若需要做括号不匹配的错误检测，只需要在碰到右括号、游标越界的分支中增加异常抛出逻辑即可，改动成本极低。

内容的提问来源于stack exchange，提问作者David542