在方案中使用两个递归调用函数转换函数使其成为尾递归

Question

在我开始之前：YES，这是来自大学的作业。在我被告知我是懒惰和邪恶的之前：作业的这一部分是转换我们已有的两个功能，这一个是第六个。

(define (flatten-list a-list) 
    (cond ((null? a-list) '()) 
     ((list? (car a-list)) 
     (append (flatten-list (car a-list)) (flatten-list (cdr a-list)))) 
     (else (cons (car a-list) (flatten-list (cdr a-list)))))) 

正如你所猜测的那样，即使它是嵌套的，该函数也会展平一个列表。我的具体转换问题出现在（list？（car a-list））条件中，其中我正在执行两个递归调用。我已经做了斐波那契，我可以通过在尾递归上只有两个“acummulators”来做到这一点。但是，我的头脑没有接受过这方面的培训，但却不知道应该如何去做。

如果给我提示而不是结果，我将不胜感激。谢谢！

Answer 1

这里是我的解决方案：

(define (flatten-iter a-list) 
    (define (flat-do acc lst-interm lst) 
    (cond 
     ((null? lst) 
     (reverse acc)) 
     ((and (list? lst-interm) (not (null? lst-interm))) 
     (flat-do acc (car lst-interm) (append (cdr lst-interm) lst))) 
     ((not (list? lst-interm)) 
     (flat-do (cons lst-interm acc) empty lst)) 
     ((list? (car lst)) 
     (flat-do acc (car lst) (cdr lst))) 
     (else 
     (flat-do (cons (car lst) acc) empty (cdr lst))))) 
    (flat-do empty empty a-list)) 

(flatten-iter (list 1 (list 2 (list 3 4 (list 5 empty 6))) 7 8)) 
=> (1 2 3 4 5 6 7 8) 

尾recrusive功能要求，他们不会再回来，这样的话你不能用于存储程序的状态使用堆栈。而是使用函数参数在函数调用之间传递状态。因此，我们需要确定如何维持这个状态。由于我们的功能的结果是list?，所以增加一个empty列表是有意义的;我们正在为此使用acc。你可以看到它在else分支上面如何工作。但是我们应该能够处理嵌套列表。而且，当我们进一步深入时，我们应该保留嵌套列表的其余元素以供进一步处理。示例列表：(list 1 (list 2 3) 4 5)

直到(list 2 3)我们已经将1添加到累加器。由于我们不能使用堆栈，我们需要其他地方来存储列表的其余元素。而这个地方是lst的参数，其中包含要扁平化的原始列表的元素。我们只需appendlst其余元素(cdr (list 2 3))这是(list 3)，并继续清单的头，我们无意中扁平化，即我。即（汽车（名单2 3）），这只是2。现在，(and (list? lst-interm) (not (null? lst-interm)))成功，因为flat-do被称为是这样的：

(flat-do (list 1) (list 2 3) (list 4 5)) 

和条件触发此代码：

(flat-do (list 1) (car (list 2 3)) (append (cdr (list 2 3)) (list 4 5))) 

再次flat-do被称为是这样的：（平-DO（表1）2（名单3 4 5））

条件(not (list? 2))现在成功并且代码(flat-do (cons 2 1) empty (list 3 4 5))进行评价。

其余处理与else分支做，直到lst是null?和reverse上acc执行。函数然后返回反向累加器。