这个scheme函数好像是尾递归的，所以为什么会出现栈溢出

Question

我最近几年来一直在胡思乱想 scheme。我正在使用 repl.it 来玩一下。我写了这个基本函数来获取列表和 return 双向链表。列表的每个单元格都是一对，其 car 是列表元素，其 cdr 是一对，car 中的前一个元素和 cdr 中的下一个元素。第一个和最后一个元素分别将 null 作为前一项和下一项。我写的函数是尾递归的。我现在知道 scheme 实际上确实有循环语法，但是当我写它时我的印象是在 scheme 中循环的唯一方法是使用尾递归。我的代码如下：

(define (dbllink li) 
    (letrec ((step (lambda (lis prev head) 
                           (if (null? lis) 
                               head 
                               (let ((cell (cons (car lis) 
                                                 (cons prev '()))))
                                 (if (null? prev) 
                                     (step (cdr lis);<--recursive call
                                           cell 
                                           cell) 
                                     (begin (set-cdr! (cdr prev)
                                                      cell) 
                                            (step (cdr lis);<--recursive call
                                                  cell 
                                                  head ))))))))
        (step li '() '())))

我标记了我认为是仅有的两个递归调用。根据 R6RS，它们在我看来都处于尾部上下文中，但调用该函数会导致堆栈溢出。关于为什么的任何想法？

Answer 1

是的。您的代码确实是尾递归的。当我在 DrRacket 的 r6rs 中尝试这个时，我得到

(dbllink '(1 2 3 4 5)) 
; ==> #0={1 () . #1={2 #0# . #2={3 #1# . #3={4 #2# 5 #3#}}}}

这样就形成了一个圆形结构。我认为 BiwaScheme 可能会尝试打印此内容，但您无法使用尾递归打印列表结构，并且它不会检查循环列表，因此您最终会遇到堆栈溢出。

您可以通过分配结果来验证这一点，这样它就不会打印结果。

(define test (dbllink '(1 2 3 4 5))   ; ==> #void
(car test) ; ==> 1
test ; ("too much recursion" in Biwa)

这个scheme函数好像是尾递归的，所以为什么会出现栈溢出

This scheme function seems to be tail recursive, so why am I getting a stack overflow

recursion

scheme

tail-recursion