递归过程到尾递归过程

Question

我正在尝试从我已经构建的另一个过程中构造一个尾递归过程。但我并没有完全意识到我应该如何思考。我给出了两个例子，第一个是我的过程，不是尾递归，第二个是我“尝试”做一个尾递归过程。嗯..。我很乐意听取任何关于如何构造尾递归过程、如何开始、如何思考以及其他方面的建议。

编辑:第一个完全符合我的要求。(define square (lambda (x) (* x x)))

(do-to-each square '(1 2 3))应该对每一个数字进行平方，这就是(1 4 9)列表

(define do-to-each
  (lambda (proc lst)
    (if (list-empty? lst)
        (list-create)
          (list-insert (proc (list-first lst)) (do-to-each proc (list-rest lst))))))

(define do-to-each-tail
  (lambda (proc lst)
    (define loop
      (lambda (n result)
        (if (= n 1)
            (list result)
            (if (eq? (length result) 1)
                (car result)
                (loop (- n 1) (cons (car result) (do-to-each-tail proc (cdr result))))))))
    (loop (length lst) lst)))

Answer 1

不需要跟踪长度、索引等，因为我们可以编写一个尾递归解决方案，直接在输入列表上迭代，积累结果，并(只为了保持顺序)在结果结束时反转结果。

例如，使用列表操作的表示法，这就是可能的解决方案的样子--并注意到我们如何使用累积结果的初始值调用循环助手过程，然后我们将reverse输出：

(define do-to-each-tail
  (lambda (proc lst)
    (define loop
      (lambda (lst result)
        (if (list-empty? lst)
            result
            (loop (list-rest lst)
                  (list-insert (proc (list-first lst)) result)))))
    (reverse (loop lst (list-create)))))

它如预期的那样运作：

(do-to-each-tail square '(1 2 3))
=> '(1 4 9)