递归与尾递归

Question

我对函数式编程很陌生，尤其是下面使用的Scheme。我正在尝试使以下函数是递归的，尾递归的。基本上，该函数的作用是对两个字符串的对齐方式进行评分。当给定两个字符串作为输入时，它会比较每个“列”字符，并根据在称为 scorer 的函数中实现的评分方案（由下面的代码中的函数调用）来累积该对齐的分数。

我有一个想法，用一个帮助函数来累积分数，但我不太确定如何去做，因此我该如何让下面的函数尾递归呢？

(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开始。我们还有一个索引（也从0开始），它跟踪要抓取的字符串中的哪个位置。当我们到达任一字符串的末尾时，基本情况是返回迄今为止累积的得分。

Answer 2

我只是想用字符列表对Chris的答案做一个修改:

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

停在那里没有用。因为这已经成为列表迭代，我们可以使用更高阶程序。通常，我们需要一个< code>fold-left或< code>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中它总是尾部递归的。