我正在使用Racket,但这个问题适用于任何支持尾递归的方案。
我熟悉在平面列表上实现尾递归的传统模式,大致如下所示:
(define (func x [acc null])
(if (null? x)
acc
(func (cdr x) (cons (do-something-to (car x)) acc))))
在这种情况下,func
处于尾部位置。
但是当我使用一棵树时,即一个带有递归嵌套列表的列表,我最终会像这样map
进行递归下降:
(define (func2 x)
(cond
[(atom? x) (do-something-to x)]
[(list? x) (map func2 x)]))
这有效,但func2
不再处于尾部位置。
你能——如果是这样,你会如何——以尾部递归的方式重写func2
吗?
(撇开它是否提高性能的问题不谈,这不是我要问的问题。
正如在另一个答案中已经正确陈述和解释的那样,对此使用尾递归没有任何好处。但是,由于您对它的完成方式感兴趣,因此这是我实现过一次的deep-map
功能。如果您对镜像列表感到满意,则代码会更干净。
(define deep-map
(λ (f lst)
(let tail-rec ([stack `(,lst)] [acc '(())])
;(displayln (~a "Stack: " stack " / Acc: " acc))
(cond [(null? (car stack))
(if (null? (cdr stack))
(car acc)
(tail-rec (cdr stack)
`(,(append (cadr acc) `(,(car acc))) . ,(cddr acc))))]
;; The first element is a list and is being put on the stack
[(list? (caar stack))
(tail-rec `(,(caar stack) . (,(cdr (car stack)) . ,(cdr stack)))
`(() . ,acc))]
;; Process next element
[else (tail-rec `(,(cdar stack) . ,(cdr stack))
`(,(append (car acc) `(,(f (caar stack)))) . ,(cdr acc)))]
))))
一个简单的例子:
> (deep-map add1 '(1 ((2) 3)))
Stack: ((1 ((2) 3))) / Acc: (())
Stack: ((((2) 3))) / Acc: ((2))
Stack: (((2) 3) ()) / Acc: (() (2))
Stack: ((2) (3) ()) / Acc: (() () (2))
Stack: (() (3) ()) / Acc: ((3) () (2))
Stack: ((3) ()) / Acc: (((3)) (2))
Stack: (() ()) / Acc: (((3) 4) (2))
Stack: (()) / Acc: ((2 ((3) 4)))
'(2 ((3) 4))
从技术上讲,您可以通过引入充当堆栈的累加器来"可以"。只有当堆栈为空时,您的函数才会完成。
但是,这与使用函数调用堆栈(即非尾递归)具有相同的内存使用要求,因此通常这样做不会获得任何好处。