In 91

題目

Write a recursive function to determine if the elements of a list form a palindrome(迴文: 從左讀與從右讀都一樣). For example:
palindrome : List -> Bool
> (palindrome ‘(1 1 2 2 3 3))
#f
> (palindrome ‘(1 2 2 2 1))
#t
> (palindrome ‘(1 a b a 1))
#t
Note : For simplicity, you may assume that the list to check contains only atoms. I.e., no nested list and you can use “eq?” to test for equality

問題簡單講
參數是一個list，我們的function會回傳 此list是否具備迴文的特性。

想法
絕大部分人一開始的想法應該跟我一樣，這要寫啥recursive ? 不是一行reverse就搞定了嘛？

	(define (palindrome-reverse a-list)
  (equal? a-list (reverse a-list)))

ya...沒錯，的確這樣一行就可以滿足我們的需求。

不過題目提到，請自己寫一個recursive function去做，
上課也一再提到，這些內建的function，也是由一個一個更小的scheme function組成的high-order function。

所以，就動手寫一下自己的reverse function吧~

設計recursive function想法

1. 判斷迴文，也就是list倒過來要等於自己，return true，不等於則return false。
2. recursive設計想法，怎麼倒過來：
   一樣，滿足tail-recursion，我們先用一個accumulating parameter，來放每一次的暫存結果。
   每次取(car list)，然後要注意append的順序，是要加在result的前面，還是後面。
   我們既然要倒著做，那就是要(append (這次car list的element) result)
3. 當list被cdr空了，則代表全部取完了，return我們的結果

所以我寫的code長這樣：

	;case 1: (palindrome '(1 1 2 2 3 3)) => #f
;case 2: (palindrome '(1 2 2 2 1)) => #t
;case 3: (palindrome '(1 a b a 1)) => #t
(define (tailReverse a-list result)
  (if (null? a-list) 
      result
      (tailReverse (cdr a-list) (append (list (car a-list)) result)))
)

(define (palindrome a-list)
  (equal? a-list (tailReverse a-list '()))    
)

blog 與課程更新內容，請前往新站位置：http://tdd.best/