如何用Scheme递归实现求整数最大两个数位之和的功能

转换思路 #

你现有版本本质是尾递归实现，Scheme标准要求必须对尾递归做优化，所以你的代码本身执行效率和命令式语言的迭代写法完全一致。如果需要写非尾递归的结构递归版本，可参考以下逻辑：

• 递归核心是拆分问题：将当前整数拆为最低位、剩余高位两部分
• 新增的辅助函数作用为：接收整数参数，返回该整数所有数位中最大、第二大的数值组成的二元列表
• 递归终止条件：当参数只剩个位数时，返回(list 当前数位 0)
• 递归流程：先递归计算剩余高位的前两大数位，再将当前最低位和这两个值比较，更新得到新的前两大值返回
• 主函数最终将辅助函数返回的两个值相加得到结果

递归实现代码 #

(define (largest-sum n)
  ; 辅助函数：返回输入整数数位的前两大值
  (define (top-two num)
    (let ((current-digit (remainder num 10))
          (rest-num (quotient num 10)))
      (cond
        ((= rest-num 0) (list current-digit 0))
        (else
         (let* ((rest-top-two (top-two rest-num))
                (first-max (car rest-top-two))
                (second-max (cadr rest-top-two)))
           (cond
             ((>= current-digit first-max) (list current-digit first-max))
             ((>= current-digit second-max) (list first-max current-digit))
             (else rest-top-two)))))))
  (apply + (top-two (abs n))))

注：代码中加入了abs处理负数输入，不需要可直接去掉。

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