方案：递归和列表

Question

我一直在尝试通过阅读教科书《如何为方案设计程序》来自学一些编程。到现在为止我已经经历了一切。问题是这样的：

9.5.5 开发转换功能。它消耗一个数字列表并且 产生相应的数字。这 第一个数字是最不重要的， 等等。

经过前几个步骤，从数据分析到模板，我结束了 到此为止，程序的基本框架是：

;; A list-of-numbers is either 1. an empty list, empty, or 2. (cons n 
lon) where n is a number and lon is a list of numbers 
;; convert : lon -> number 
;; to consume a lon and produce the corresponding number. The least 
significant digit corresponds to the first number in the list, and so 
on. 
;; (= (convert (cons 1 (cons 9 (cons 10 (cons 99 empty))))) 991091) 
(define (convert lon) 
  (cond 
    [(empty? lon)...] 
    [(cons? lon)...(first lon)...(convert (rest lon))...])) 

我如何度过这个阶段，正如书中所说的那样，“组合价值观”？ 我认为可行的一种方法是将第一个值乘以 10 的值在总数中的重要性的幂，例如，

(cons 1 (cons 9 空)) => 1 * 10^(显着性)，其中最小 重要性将为 0。用我有限的理解 编程，我认为需要一些计数器，其中 n 增加 从某种意义上说，每次调用该函数时都会有一个 递归地。但在我看来，这是一次尝试运行两个 同时递归。因为表达式被求值 按顺序（显然），你不能像你一样调用计数器函数 调用转换函数。

那么，有人可以帮我解决这个问题吗？我更愿意如果你 使用自然递归和列表的 CONStructor 解决了这个问题 不是 lambda 或本书尚未讨论的其他想法。

谢谢！

Answer 1

您不需要进行求幂 - 简单的乘法就可以了。

(define (convert digits) 
  (cond
    ((empty? digits) 0)
    (else (+ (* 10 (convert (rest digits))) (first digits)))
  )
)

(convert '(1 2 3 4 5 6))

或者，换一种思考方式：

(define (convert digits)
  (convert-helper digits 1 0)
)

(define (convert-helper digits multiplier sofar)
  (cond
    ((empty? digits) sofar)
    (else 
        (convert-helper 
            (rest digits) 
            (* 10 multiplier) 
            (+ (* multiplier (first digits)) sofar)
        )
    )
  )
)


(convert '(1 2 3 4 5 6))

Answer 2

这是尾递归版本：

(define (convert lon)
  (let rec ((i 0)
            (n 0)
            (lon lon))
    (cond ((empty? lon) n)
          (else (rec (+ i 1)
                     (+ n (* (first lon) (expt 10 i)))
                     (rest lon))))))