12

出于某种原因，我很难想出一种重写此函数的好方法，以便它使用恒定的堆栈空间。大多数关于树递归的在线讨论都是通过使用斐波那契函数并利用该特定问题的属性来作弊的。有没有人对递归的这种“真实世界”（嗯，比斐波那契数列更真实）使用有任何想法？

Clojure是一个有趣的案例，因为它没有尾调用优化，而只有通过“recur”特殊形式的尾递归。它还强烈反对使用可变状态。它确实有许多惰性结构，包括tree-seq，但我看不到它们如何帮助我解决这种情况。谁能分享他们从 C、Scheme、Haskell 或其他编程语言中学到的一些技术？

(defn flatten [x]
  (let [type (:type x)]
    (cond (or (= type :NIL) (= type :TEXT))
          x
          (= type :CONCAT)
          (doc-concat (flatten (:doc1 x))
                      (flatten (:doc2 x)))
          (= type :NEST)
          (doc-nest (:level x)
                    (flatten (:doc x)))
          (= type :LINE)
          (doc-text " ")
          (= type :UNION)
          (recur (:doc1 x)))))

编辑：根据评论中的要求...

用一般术语重述并使用 Scheme——如何重写以下递归模式，使其不消耗堆栈空间或需要对非自调用进行尾调用优化？

(define (frob x)
  (cond ((foo? x)
         x)
        ((bar? x)
         (macerate (f x) (frob (g x))))
        ((thud? x)
         (frobnicate (frob (g x))
                     (frob (h x))))))

我选择了烦人的名字来说明我正在寻找不依赖于 x、浸渍、frobnicate、f、g 或 h 的代数属性的答案。我只想重写递归。

更新：

Rich Hickey为 Clojure添加了一个显式的蹦床函数。

4

7 回答 7

6

请不要对此投反对票，因为它很难看。我知道这很丑。但这是一种以蹦床风格（没有系统堆栈溢出）并且不使用 goto 的方法。

push x,1 on homemade stack
while stack length > 1
  n = pop
  if (n==1)
    x = pop
    if (type(x)==NIL || type(x)==TEXT)
      push x // this is the "return value"
    else if (type(x)==CONCAT)
      push 2 // say call doc-concat
      push doc2(x), 1 // 2nd recursion
      push doc1(x), 1 // 1st recursion
    else if (type(x)==NEST)
      push 3 // say call doc-nest
      push level(x) // push level argument to doc-nest
      push doc(x), 1 // schedule recursion
    else if (type(x)==LINE)
      push " " // return a blank
    else if (type(x)==UNION)
      push doc1(x), 1 // just recur
  else if (n==2)
    push doc-concat(pop, pop) // finish the CONCAT case
  else if (n==3)
    push doc-nest(pop, pop) // finish the NEST case
  endif
endwhile
// final value is the only value on the stack
于 2008-11-25T00:32:43.403 回答
3

轻松转换算法的主要障碍是它不会导致对同一函数的一系列调用；但在几个之间交替，每个都对另一个的结果进行操作。

我会说你有三个选择：

  1. 完全重新制定算法（这就是斐波那契示例所做的）。
    • 将所有函数组合成一个带有大量 cond 的函数（丑陋，并且可能不会导致真正的尾递归，即使使用单个函数）。
    • 将流程由内而外：编写一个简单的尾递归函数，将输入数据转换为必须执行的操作序列，然后对其进行评估。
于 2008-11-24T22:10:51.320 回答
2

如果 flatten 两次调用自身（在 :CONCAT 的情况下），它如何变成一个循环？也许我错过了一些东西。似乎它本质上是一个树行走。

我的意思是，有一些方法可以在没有堆栈的情况下进行树遍历，但必须是无界的，例如使用 FIFO 进行，或者按照建议使用延续。

于 2008-11-24T22:53:18.330 回答
2

您可以使用延续传递：

(define (frob0 x k)
  (cond ((foo? x)
         (k x))
        ((bar? x)
         (frob0 (g x) 
           (lambda (y) 
             (k (macerate (f x) y))))
        ((thud? x)
         (frob0 (g x) 
           (lambda (y)
             (frob0 (h x) 
               (lambda (z)
                 (k (frobnicate y z))))))))

(define (frob x)
  (frob0 x (lambda (y) y))

这不会让事情更容易理解:-(

于 2008-11-24T23:29:31.067 回答
2

标准的通用技术是转换为蹦床风格。对于您的特定问题（实现漂亮打印组合器），您可能会发现 Derek Oppen 1980 年的论文“Prettyprinting”（不在网络 AFAIK 上）很有帮助。它提出了一种基于堆栈的命令式算法，类似于 Wadler 后来的函数式算法。

于 2008-11-25T00:34:26.583 回答
0

我能想到的最好的是这样的：

(define (doaction vars action)
  (cond ((symbol=? action 'frob)
         (cond ((foo? (first vars))
                (first vars))
               ((bar? (first vars))
                (doaction (list (f (first vars)) (doaction (g x) 'frob)) 'macerate)
etc...

它不是完全尾递归的，但可能是你能得到的最好的。总拥有成本确实是要走的路。（我知道由于 JVM，Clojure 不能拥有它）。

于 2008-11-25T00:06:50.977 回答
0

以下不是您问题的具体答案，但希望这将是一个有用的示例。它用一堆任务替换了多个递归（否则需要一个无界的调用堆栈）。

（在 Haskellish 代码中）： 

data Tree = Null | Node Tree Val Tree



-- original, non-tail-recursive function:
flatten :: Tree -> Result
flatten Null = nullval
flatten (Node a v b) = nodefunc (flatten a) v (flatten b)



-- modified, tail-recursive code:
data Task = A Val Tree | B Result Val



eval :: Tree -> [Task] -> Result
use  :: Result -> [Task] -> Result



eval Null tasks = use nullval tasks
eval (Node a v b) tasks = eval a ((A v b):tasks)



use aval ((A v b):tasks) = eval b ((B aval v):tasks)
use bval ((B aval v):tasks) = use (nodefunc aval v bval) tasks
use val [] = val



-- actual substitute function
flatten2 :: Tree -> Result
flatten2 tree = eval tree []

于 2008-11-26T00:32:06.680 回答