如何使该方案功能不尾递归？

Question

我不知道如何使此尾部递归方案功能不再尾部递归。谁能帮助我？

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

Answer 1

left折叠在继承上是迭代的，但是您可以通过添加连续来轻松地使它们递归。例如。

(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
      (cons (proc (car lst))
            (fold-right proc tail (cdr lst)))))

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

[还要注意，当将过程称为proc时，看一下参数在何处，结果tail的尾部和列表参数lst会更简单。您甚至不需要阅读我的代码即可知道如何使用它，但是您不知道x和u是什么，并且ti不利于参数顺序不遵循任何fold实现在Scheme中已知。