recursion - 方案:将递归改为尾递归

Question

我不确定如何将向前计数变成尾递归程序。它接受一个非负数 n，并返回从 0 到 n 的整数列表(包括 n >)。

编辑:好的，我终于让这个工作了。问题不在于我当前的程序是递归的，而我需要使其成为尾递归的——这完全是错误的。实际的答案非常简短明了。因此，如果其他人被困在这个问题上并且也是一个完全的编程菜鸟，这里有一些可能会有所帮助的提示:

1) 您的帮助程序旨在跟踪到目前为止的列表。

2) 它的基本情况是.. 如果 x = 0.. 你会做什么？添加 0 到..某物上。

3) 在 x - 1 上重复，然后将 x 添加到您的列表中。

4) 当您进入实际程序时，向前倒数，您所需要的只是助手。但请记住，它需要两个参数!

Answer 1

这里唯一的递归函数是 list-reverse。它是尾递归的，因为对自身的调用是函数体中的最后一个操作。

用于生成从零到 m 的非递减序列的函数，其中包含将 1 添加到前一个元素的连续结果，如下所示:

(define (my-reverse lst)
  (define (rev-do xs ys)
    (if (empty? xs)
        ys
        (rev-do (cdr xs) (cons (car xs) ys))))
  (rev-do lst empty))

(define (seq m n)
  (seq-do m n (list m)))

(define (seq-do m n xs)
  (if (= m n)
      (my-reverse xs)
      (let ((next (add1 m)))
        (seq-do next n (cons next xs)))))

(define (seq-from-zero m)
  (seq 0 m))

测试:

> (seq-from-zero 10)
(0 1 2 3 4 5 6 7 8 9 10)

seq-do 是生成从 m 到 n 的非递减序列的通用函数；它是尾递归的，因为最后一个操作是对其自身的调用。

我还从头开始实现了reverse，以便您可以在作业问题中使用它。