球拍：列表上的尾遞歸輸出反向列表

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)))