重写这种非尾递归函数有什么好方法？

Question

出于某种原因,我无法想出一个重写此函数的好方法,因此它使用不变的堆栈空间.大多数关于树递归的在线讨论都是通过使用Fibonacci函数并利用该特定问题的属性来作弊.有没有人对这个"真实世界"(嗯,比Fibonacci系列更现实世界)使用递归有任何想法？

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,macerate,frobnicate,f,g或h的代数属性的答案.我只是想重写递归.

更新:

Rich Hickey已经向Clojure 添加了一个明确的蹦床功能.

Answer 1

请不要贬低这个,因为它很难看.我知道这很难看.但这是一种在trampoline风格(没有系统堆栈溢出)和不使用gotos的方式.

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