遞歸與VS.尾遞歸

Question

我對函數式編程頗爲陌生，特別是下面使用的Scheme。我試圖讓下面的函數是遞歸的，尾遞歸的。 基本上，函數做什麼，是分數兩個字符串的對齊。當給定兩個字符串作爲輸入時，它會比較每個字符的「列」，並根據評分方案累積該比對的評分，該評分方案在名爲scorer的函數中實現，該函數由以下代碼中的函數調用。

我有點用輔助函數來積累分數的想法，但我不太清楚該怎麼做，所以我該如何去做這個函數在tail-recursive下面呢？

(define (alignment-score string_one string_two) 
    (if (and (not (= (string-length string_one) 0)) 
      (not (=(string-length string_two) 0))) 
     (+ (scorer (string-ref string_one 0) 
       (string-ref string_two 0)) 
     (alignment-score-not-tail 
      (substring string_one 1 (string-length string_one)) 
      (substring string_two 1 (string-length string_two)) 
     ) 
     ) 
    0) 
) 

Answer 1

下面是它會是什麼樣子與蓄電池：

(define (alignment-score s1 s2) 
    (define min-length (min (string-length s1) (string-length s2))) 
    (let loop ((score 0) 
      (index 0)) 
    (if (= index min-length) 
     score 
     (loop (+ score (scorer (string-ref s1 index) 
           (string-ref s2 index))) 
       (+ index 1))))) 

在這種情況下，score是累加器，開始爲0。我們也有一個index（也開始爲0），保持跟蹤要抓取的字符串中的哪個位置。基本情況下，當我們到達任一字符串的末尾時，返回到目前爲止累計的score。

Answer 2

只是想使用字符的名單克里斯的回答的一個變種：

(define (alignment-score s1 s2) 
    (let loop ((score 0) 
      (l1 (string->list s1)) 
      (l2 (string->list s2))) 
    (if (or (null? l1) (null? l2)) 
     score 
     (loop (+ score (scorer (car l1) 
           (car l2))) 
       (cdr l1) 
       (cdr l2))))) 

沒有使用止步。由於這現在已經成爲列表迭代，我們可以使用更高階的程序。通常，我們希望有一個fold-left或foldl和SRFI-1 fold就是一個很好的實現，不需要列表以相同的長度：

; (import (scheme) (only (srfi :1) fold)) ; r7rs  
; (import (rnrs) (only (srfi :1) fold)) ; r6rs  
; (require srfi/1)      ; racket 

(define (alignment-score s1 s2) 
    (fold (lambda (a b acc) 
      (+ acc (scorer a b))) 
     0 
     (string->list s1) 
     (string->list s2))) 

如果積累和順序並不重要，總是選擇左折因爲它總是在Scheme中進行尾遞歸。