0

我不知道如何使这个尾递归方案函数不再是尾递归。任何人都可以帮助我吗？

(define (foldrecl f x u)
  (if (null? x)
      u 
      (foldrecl f (cdr x) (f (car x) u))))
4

3 回答 3

1

左折叠是继承迭代的，但您可以通过添加延续轻松使它们递归。例如。

(let ((value expresion-that-calculates))
  value)

所以在你的情况下：

(define (foldrecl f x u)
  (if (null? x)
      u 
      (let ((result (foldrecl f (cdr x) (f (car x) u))))
        result)))

虽然这看起来很有希望，但它并不能保证一个智能的 Scheme 实现会计算出result刚刚返回的并将其改为尾调用。右折叠更容易，因为它们本质上是递归的：

(define (fold-right proc tail lst)
  (if (null? lst)
      tail
      (proc (car lst)
            (fold-right proc tail (cdr lst)))))

在这里，您清楚地看到递归部分需要成为参数cons，因此除非是基本情况，否则永远不会处于尾部位置。

proc另请注意，查看调用过程时的参数、结果的尾部tail和列表参数会稍微简单一些lst。你甚至不需要阅读我的代码就知道如何使用它，但你的我不知道什么x和uti 并没有帮助参数顺序不遵循foldScheme 中已知的任何实现。

于 2019-09-26T22:52:49.557 回答
1

递归调用位于尾部位置，因此将其放在另一个过程调用中，如下所示：

(define (identity x) x)

(define (foldrecl f x u)
  (if (null? x)
      u 
      (identity (foldrecl f (cdr x) (f (car x) u)))))

现在递归调用不在尾部位置，它不再是尾部递归。

如果编译器知道它什么都不做，但希望它不会做，则允许编译器优化标识函数。

于 2019-09-27T11:28:35.297 回答
0

与其做，不如为做做计划；只有在最后，做：

(define (foldreclr f xs a)
  (define (go xs)
     (if (null? xs) 
        (lambda (a) a)
        (let ((r (go (cdr xs))))    ; first, recursive call;
           (lambda                  ; afterwards, return a plan:
                  (a)               ;    given an a, to
             (r                     ;    perform the plan for (cdr xs)
               (f (car xs) a))))))  ;    AFTER processing (car x) and a.
  ((go xs)                          ; when the overall plan is ready,
           a))                      ;    use it with the supplied value

内部函数go遵循正确的折叠模式。它首先进行递归调用，然后才组合并返回一个值，该计划首先将列表的头部元素与累加器值组合，然后执行列表尾部的计划——就像原来的foldrecl那样。

当整个列表变成行动计划时，最终执行该行动以转换提供的初始累加器值——执行与原始foldrecl左折叠相同的计算。

这被称为向右倾斜，您再次向左倾斜。(*)

> (foldreclr - (list 1 2 3 4) 0)   ; 4-(3-(2-(1-0)))
2
> (foldreclr - (list 4 3 2 1) 0)   ; 1-(2-(3-(4-0)))
-2

也可以看看：

（抱歉，这些在 Haskell 中，但 Haskell 也是 Lisp。）

于 2019-09-30T15:00:24.413 回答