相关疑难解决方法(0)

一个reddit线程提出了一个显然有趣的问题:

尾递归函数可以简单地转换为迭代函数.其他的,可以通过使用显式堆栈进行转换.可每次递归转化为迭代？

帖子中的(计数器？)示例是对:

(define (num-ways x y)
  (case ((= x 0) 1)
        ((= y 0) 1)
        (num-ways2 x y) ))

(define (num-ways2 x y)
  (+ (num-ways (- x 1) y)
     (num-ways x (- y 1))

尾递归是函数式语言中一个重要的性能优化策略,因为它允许递归调用消耗常量堆栈(而不是O(n)).

是否有任何问题根本无法以尾递归方式编写,或者总是可以将天真递归函数转换为尾递归函数？

如果是这样,有一天功能编译器和解释器可能足够智能以自动执行转换？

是否有可能在O(1)辅助空间中迭代二叉树(没有使用堆栈,队列等),或者这被证明是不可能的？如果有可能,怎么办呢？

编辑:如果有关于父节点的指针很有趣并且我不知道这可以做到,那么我得到的关于这可能的响应是可能的,但是根据你如何看待它,可以是O(n)辅助空间.此外,在我的实际用例中,没有指向父节点的指针.从现在开始,请在回答时假设这一点.

我正在学习haskell,我看到的函数定义是:

quickSort (x : xs) = (quickSort less) ++ (x : equal) ++ (quickSort more)
                 where less = filter (< x) xs
                       equal = filter (== x) xs
                       more = filter (> x) xs

是否可以只用一次遍历列表而不是3来编写它？