球拍：列表上的尾递归输出反向列表

Question

我希望我的函数能够对给定列表中的每个数字进行平方，而且，如果lst中的 元素是列表，则该函数将递归应用于该元素并对元素进行操作该名单也是如此。

这是我的代码：

(define (sqr-up-rec-tail lst) 
    (define (helper lst newlist) 
    (if (null? lst) newlist 
     (if (list? (car lst)) 
      (helper (cdr lst) (cons (sqr-up-rec-tail (car lst)) newlist)) 
      (helper (cdr lst) (cons (* (car lst) (car lst)) newlist))))) 
    (helper lst())) 

我的函数的工作，但是，我得到一个相反的平方列表。 例如，当我运行：

（SQR-UP-REC-尾“（2 4 6（10 20）））

输出I得到的是：

（（400 100）36 16 4）

我想用的外部反向功能以获得正确的输出而不。我的猜测是，我应该使用append而不是cons，尽管我没有得到它的工作。

谢谢。

Answer 1

append可以工作，但要记住，让你的函数O（N²）的时间，因为追加基本上是这样的：

(define (append a b) 
    (if (null? a) 
     b 
     (cons (car a) 
      (append (cdr a) b)))) 

由于append是这样一个糟糕的O（n）的时间和空间。它将使您的结果算法O（n²）的时间和空间，因为您将它用于每个子列表直到结果的完整列表。

既然你已经有了一个帮手你可以用它来使自己的reverse：

(define (reverse-helper from to) 
    (if (null? from) 
     to 
     (reverse-helper (cdr from) (cons (car from) to)))) 

并返还的(helper lst '())你做(reverse (helper lst '()) '())结果代替。

Answer 2

这里使用尾递归的问题是，得到处理的第一个元素最终成为新列表中的最后一个元素，因此需要像append和reverse这样的过程。您可以使用append或reverse避免尾递归构建过程没有，如下：

(define (map-sqr lst) 
    (cond 
    [(null? lst) empty] 
    [(pair? (car lst)) 
    (cons (map-sqr (car lst)) 
      (map-sqr (cdr lst)))] 
    [else 
    (cons (* (car lst) (car lst)) 
      (map-sqr (cdr lst)))])) 

但是，如果你必须使用尾递归，然后为你指出的，append可以使用，而累计获得期望的输出，如下所述：

(define (map-sqr-tail lst) 
    (let loop ([lst lst] 
      [new-lst '()]) 
    (cond 
     [(null? lst) new-lst] 
     [(pair? (car lst)) 
     (loop (cdr lst) 
      (append new-lst (list (loop (car lst) empty))))] 
     [else 
     (loop (cdr lst) 
      (append new-lst (list (* (car lst) (car lst)))))]))) 

两种实现按预期：

> (map-sqr '(2 4 6 (10 20 (30)))) 
'(4 16 36 (100 400 (900))) 
> (map-sqr-tail '(2 4 6 (10 20 (30)))) 
'(4 16 36 (100 400 (900)))