Scheme:将递归更改为尾递归

Question

我不确定如何将count-forwards转变为尾递归程序.它需要一个非负数,n并返回一个整数从列表中0,以n(其中包括n).

编辑:好的,我终于让这个工作了.问题不是我当前的程序是递归的,我需要让它尾递归 - 这是完全错误的.实际答案非常简洁.所以如果其他人都坚持这个并且也是一个完整的编程菜鸟,这里有一些提示可能会有所帮助:

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

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

3)重复x - 1,然后到目前为止将x添加到列表中.

4)当你到达实际的程序时,你需要的只是帮助者.但请记住,这需要两个参数!

Answer 1

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

用于生成从0到0的非递减序列的函数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从零开始实施,以便您可以在作业问题中使用它.