Scheme尾递归与解码树：递归差异、代码优化及错误排查

尾递归与普通递归的核心区别 #

普通递归在递归调用执行完成后，还需要执行额外运算（比如对返回结果做拼接、计算等操作），调用栈需要保存每一层的上下文信息，递归深度过大时会出现栈溢出。
尾递归的核心要求是：递归调用是当前函数执行的最后一个操作，函数不需要保留当前层的上下文，可以直接把递归调用的结果作为当前层的返回值，解释器可以将其优化为迭代执行，不会占用额外的栈空间。

原decode函数不属于尾递归的原因 #

原代码中当next-branch判断为叶子节点时，执行的逻辑是：

(cons (symbol-leaf next-branch)
  (decode-1 (cdr bits) tree))

decode-1递归调用返回后，还需要执行cons操作把叶子符号拼接到结果开头，递归调用不是当前分支的最后一个操作，不符合尾递归要求。只有非叶子节点分支的decode-1调用是尾递归，叶子分支不满足，因此整个函数不属于尾递归。

你编写的decode2存在的问题 #

一共3处明显错误：

• 初始调用逻辑错误：末尾的(decode-1 '() tree res)写法有两个问题，一是初始调用时res还未定义，二是应该传入原始的bits参数而非空列表，初始的结果容器应该是空列表'()
• 非叶子分支参数错误：非叶子节点场景下，下一层递归的当前分支应该是next-branch，你错误写成了tree，会导致每次走到非叶子节点都重新从根节点遍历，逻辑完全错误
• 拼写错误：(symbol-leaf next branch)多了空格，应该是next-branch，会触发变量未定义的报错

修正后的尾递归版本 #

(define (decode-tail bits tree)
  (define (decode-1 bits current-branch res)
     (if (null? bits)
       (reverse res)
       (let ((next-branch
            (choose-branch (car bits) current-branch)))
            (if (leaf? next-branch)
                (decode-1 (cdr bits) tree (cons (symbol-leaf next-branch) res))
                (decode-1 (cdr bits) next-branch res)))))
  (decode-1 bits tree '()))

该版本所有分支的最后一个操作都是decode-1的递归调用，完全符合尾递归要求，不需要保存每层上下文，递归深度再大也不会出现栈溢出。

内容的提问来源于stack exchange，提问作者N.A.