使用尾端递归重写通用功能

发布于 2025-01-19 12:01:00 字数 452 浏览 1 评论 0原文

我一直在尝试修改此代码，以使用尾端递归重写“重复”功能，但在我的尝试中遇到了一些陷入困境。

(define (repeat n x)
  (if (= n 0)
      '()
      (cons x (repeat (- n 1) x))))

这是原始的“重复”功能。它穿过“ n -1”递归级别，然后将“ x”附加到“ n”其他递归调用中的列表中。而是应进行递归调用，并应同时将'X'拨打到列表中。

(define (repeat-tco n x)
  (trace-let rec ([i 0]
                  [acc '()])
    (if (= i n)
        acc
        (rec (+ i 1) (cons x acc)))))

这是我想出的最接近的重写版本，我相信遵循尾声递归，但我不确定。

原文

I've been trying to tinker with this code to rewrite a "repeat" function using tail-end recursion but have gotten a bit stuck in my attempts.

(define (repeat n x)
  (if (= n 0)
      '()
      (cons x (repeat (- n 1) x))))

This is the original "repeat" function. It traverses through 'n - 1' levels of recursion then appends 'x' into a list in 'n' additional recursive calls. Instead of that, the recursive call should be made and the 'x' should be appended to a list at the same time.

(define (repeat-tco n x)
  (trace-let rec ([i 0]
                  [acc '()])
    (if (= i n)
        acc
        (rec (+ i 1) (cons x acc)))))

This is the closest rewritten version that I've come up with which I believe follows tail-call recursion but I'm not completely sure.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

梦幻的味道 2025-01-26 12:01:00

您的重复TCO函数确实是尾部递归的：这是因为递归调用rec在“尾部位置”中：在称为的点，函数称其为返回该呼叫的价值之外别无他法。

[以下是一些有用的事情：答案是上面的，但是本质上“是”的答案似乎太短了

。 （Cons ...（p ...））并将其转换为具有额外的“累加器”参数的过程，然后尾部递归非常普遍。使用此技术的结果是结果向后出现：这对您来说并不重要，因为列表的所有元素都是相同的，但是想象一下：

(define (evens/backwards l)
  (let loop ([lt l]
             [es '()])
    (if (null? lt)
        es
        (loop (rest lt)
              (if (even? (first lt))
                  (cons (first lt) es)
                  es)))))

这将返回其参数的均匀元素，而是向后返回。如果您希望他们正确地走，那么可怕的答案是

(define (evens/terrible l)
  (let loop ([lt l]
             [es '()])
    (if (null? lt)
        es
        (loop (rest lt)
              (if (even? (first lt))
                  (append es (list (first lt)))
                  es)))))

（为什么是一个可怕的答案？）正确的答案是

(define (evens l)
  (let loop ([lt l]
             [es '()])
    (if (null? lt)
        (reverse es)
        (loop (rest lt)
              (if (even? (first lt))
                  (cons (first lt) es)
                  es)))))

Your repeat-tco function is indeed tail recursive: it is so because the recursive call to rec is in 'tail position': at the point where it's called, the function that is calling it has nothing left to do but return the value of that call.

[The following is just some perhaps useful things: the answer is above, but an answer which was essentially 'yes' seemed too short.]

This trick of taking a procedure p which accumulates some result via, say (cons ... (p ...)) and turning it into a procedure with an extra 'accumulator' argument which is then tail recursive is very common. A result of using this technique is that the results come out backwards: this doesn't matter for you because all the elements of your list are the same, but imagine this:

(define (evens/backwards l)
  (let loop ([lt l]
             [es '()])
    (if (null? lt)
        es
        (loop (rest lt)
              (if (even? (first lt))
                  (cons (first lt) es)
                  es)))))

This will return the even elements of its arguments, but backwards. If you want them the right way around, a terrible answer is

(define (evens/terrible l)
  (let loop ([lt l]
             [es '()])
    (if (null? lt)
        es
        (loop (rest lt)
              (if (even? (first lt))
                  (append es (list (first lt)))
                  es)))))

(Why is it a terrible answer?) The proper answer is

(define (evens l)
  (let loop ([lt l]
             [es '()])
    (if (null? lt)
        (reverse es)
        (loop (rest lt)
              (if (even? (first lt))
                  (cons (first lt) es)
                  es)))))

回复收藏 0 原文

~没有更多了~