如何使该Scheme函数不尾递归? [英] How to make this Scheme function not tail recursive?

问题描述

我不知道如何使该尾部递归Scheme函数不再是尾部递归.有人可以帮助我吗?

I can't figure out how can I make this tail recursive Scheme function not tail recursive anymore. Anyone can help me?

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

推荐答案

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

left folds are inheritly iterative, but you can easily make them recursive by adding a continuation. eg.

(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，而是使其成为尾部调用.右折是固有的递归，因此比较容易:

While this looks promising it does not guarantee that a smart Scheme implementation figures out that result is just returned and make it a tail call instead. Right folds are easier since they are inherently recursive:

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

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

Here you clearly see the recursive part needs to become a argument to cons and thus never in tail position unless it is the base case.

还要注意，在调用该过程proc时，看一下参数在哪里变了，结果tail的尾部和列表参数lst在哪里变了一点.您甚至不需要阅读我的代码即可知道如何使用它，但是您不知道x和u是什么，ti并没有帮助我们说明参数顺序不遵循任何fold实现在Scheme中已知.

Also notice it's slightly simpler to see what arguments goes where when the procedure is called proc, the tail of the result tail and the list argument lst. You don't even need to read my code to know how to use it, but yours I have no idea what x and u and ti doesn't help that the argument order doesn't follow any fold implementations known in Scheme.

这篇关于如何使该Scheme函数不尾递归?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！