计划中的尾递归计数函数

函数应该是尾递归的，并从1开始计数到指定的数。我觉得我相当接近。这是我有：计划中的尾递归计数函数

(define (countup l) 
    (if (= 1 l) 
     (list l) 
     (list 
     (countup (- l 1)) 
     l 
     ) 
    ) 
)

但是，这显然返回一个列表与嵌套列表。我试图使用附加功能而不是第二个列表无济于事。任何指导？

来源

2012-03-28 user1299108

它应该返回什么？ n个元素的列表，从1到n按升序排列，其中n是输入？ – 2012-03-28 19:39:52

是的，确切地说。按升序列出n个元素，从1到指定的数字。对不起，我不是很清楚。 – user1299108 2012-03-28 19:42:07

这不是尾巴recusive。该函数中的最后一个调用转到“列表”而不是“countup”。 – knivil 2012-03-29 07:32:30

下面是一个不正确的解决方案：

(define (countup n) 
    (define (help i) 
    (if (<= i n) 
     (cons i (help (+ i 1))) 
     '())) 
    (help 1))

该解决方案：

使用帮助功能
递归超过这一数字从1到n，利弊-ING他们在不断增长列表

为什么这是错的？这不是真正的尾递归，因为它会创建一个长长的cons调用，不能立即进行评估。这会导致堆栈溢出足够大的值n。

这里有一个更好的办法来解决这个问题：

(define (countup n) 
    (define (help i nums) 
    (if (> i 0) 
     (help (- i 1) 
       (cons i nums)) 
     nums))) 
    (help n '()))

注意事项：

这个解决方案是更好，因为到cons呼叫可以立即进行评估，所以这个功能是候选对于尾递归优化（TCO），在这种情况下堆栈空间不会成为问题。
help递归浑身解数数量，从而避免了需要使用append，这是相当昂贵的

来源

2012-03-28 19:59:38

这里你的代码的工作版本，以正确的顺序返回一个列表（我的n取代l）：

(define (countup n) 
(if (= 1 n) 
    (list n) 
    (append (countup (- n 1)) (list n))))

可悲的是，与这一段代码的一个问题：它不是尾-recursive。原因是递归调用countup不在尾部位置。它不在尾部位置，因为我正在追加(countup (- l 1))的结果，所以尾部呼叫是append（或list当n = 1）而不是countup。这意味着这段代码是一个正常的recusrive函数，但是是一个尾递归函数。

从Wikipedia检查此link可以找到更好的示例，说明它为什么不是尾部重新驱动。

为了使其成为尾递归，您需要有一个累加器负责累计计数值。这样，您就可以将递归函数调用放在尾部位置。查看我给你的链接的区别。

如果您需要更多详细信息，请不要犹豫，回复。

来源

2012-03-28 19:59:05 Matt

假设这是一个学习的过程，你想这样的行为：

(countup 5) => (list 1 2 3 4 5)

这是一个提示 - 在尾递归函数中，尾部位置的调用应该是自身的（除非它是边缘情况）。

由于countup并不包含数字列表，因此您需要一个累加器函数，它需要一个数字和一个列表，并返回一个列表。

这里是一个模板：

;; countup : number -> (listof number) 
(define (countup l) 

    ;; countup-acc : number, (listof number) -> (listof number) 
    (define (countup-acc c ls) 
    (if ... 
     ... 
     (countup-acc ... ...))) 

    (countup-acc l null))

在内部调用COUNTUP-ACC，你将需要改变是在边缘的情况下检查的说法得到它更接近边缘的情况下，和你需要改变另一个参数，以使它更接近你想要返回的结果。

来源

2012-03-28 20:00:19 twf

您应该使用辅助函数来实现此问题的尾递归解决方案（“循环”函数），并使用额外的参数来累计答案。类似这样的：

(define (countup n) 
    (loop n '())) 

(define (loop i acc) 
    (if (zero? i) 
     acc 
     (loop (sub1 i) (cons i acc))))

或者，您可以使用命名的let。无论哪种方式，该溶液是尾递归且参数被用于累积值，注意到递归前进向后，在列表的开头开始在n和计数回0，consing反过来每个值：

(define (countup n) 
    (let loop ((i n) 
      (acc '())) 
    (if (zero? i) 
     acc 
     (loop (sub1 i) (cons i acc)))))

来源

2012-03-28 21:33:38

计划中的尾递归计数函数

回答

相关问题