1

我正在尝试编写两个单独的尾递归函数来计算列表的长度，并且我有这些限制：

  1. 编写一个版本，lengtht即尾递归并根据需要使用外部（非嵌套）辅助函数

  2. 编写第二个版本，lengtht2它不使用额外的顶级函数。该函数应该仍然是尾递归的，并且可以使用您想要的任何本地绑定

我是球拍新手，这就是我理解的尾递归的一般形式：

(define (func x)
    (cond (end-test-1 end-value-1)
          (end-test-2 end-value-2)
          (else (func reduced-x))))

我只是对如何做到这一点有点困惑

4

2 回答 2

2

本质上，尾递归函数会不断调用自身，直到达到其结束条件。然而，与“常规”递归不同，它会将中间答案传递给自身，直到到达终点。

一个例子是这样的：

(define (find-length i lst)
  (if
    (null? lst) i
    (find-length (+ i 1) (cdr lst))))

该函数有两个值：i，它跟踪到目前为止列表的长度，以及lst我们正在计算元素的列表。i，出于所有意图和目的，是我们对列表中元素的运行计数。所以如果我们调用这个方法，我们会希望调用它时i初始化为 0。

首先我们检查列表是否为空。( null?) 如果列表为空，我们可以假设我们已经计算了所有元素，所以我们只需返回i，这是我们的运行计数。这是我们的最终条件。

否则，我们find-length再次调用。然而，这一次，我们增加i了 1 并从 list 中删除了第一个元素(cdr lst)。

例如，假设我们这样调用函数：

(find-length 0 (list 2 3 4 3 5 3))

正如我们评估的那样，该程序将递归调用：

(find-length 1 '(3 4 3 5 3))
(find-length 2 '(4 3 5 3))
(find-length 3 '(3 5 3))
(find-length 4 '(5 3))
(find-length 5 '(3))
(find-length 6 '()) ; end condition, return 6

这个问题通常是尾递归的一个很好的参考。

于 2012-10-10T03:45:29.433 回答
2

这看起来像家庭作业，所以我会给你一些提示，为你指明正确的方向，你可以填空。第一个问题试试这个：

(define (loop lst acc)              ; receives a list and an accumulator
  (cond ((null? lst) <???>)         ; if the list is empty return the accumulator
        (else (loop <???> <???>)))) ; advance the recursion, +1 to accumulator

(define (length1 lst)
  (loop <???> <???>))               ; how should we initialize the iteration?

试试这个第二个问题：

(define (length2 lst)
  (letrec ((loop <???>)) ; lambda with the same procedure as the previous `loop`
    (loop <???> <???>))) ; start the recursion exactly the same as in `length1`

无论如何，想一想：空（null）列表的长度是多少？答案将向您展示如何初始化迭代。对于这两种解决方案，我们都使用了一个额外的参数acc来跟踪到目前为止的答案，并将它与列表一起传递给循环尾递归过程。

于 2012-10-10T03:46:22.527 回答