方案:递归和列表

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))...])) 

我该如何度过这一阶段，就像这本书所写的，“结合价值观”？我认为唯一可行的方法是，如果我把第一个值乘以这个值在总数中的重要性的幂，例如，

(cons1(cons9空)) => 1*10^(显着性)，其中最小显着性将为0。使用我对编程的有限理解，我认为这需要一些计数器，其中n每次以某种方式被称为递归的函数时，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))))))