Recursion Vs. Tail Recursion

Question

I'm quite new to functional programming, especially Scheme as used below. I'm trying to make the following function that is recursive, tail recursive. Basically, what the function does, is scores the alignment of two strings. When given two strings as input, it compares each "column" of characters and accumulates a score for that alignment, based on a scoring scheme that is implemented in a function called scorer that is called by the function in the code below.

I sort of have an idea of using a helper function to accumulate the score, but I'm not too sure how to do that, hence how would I go about making the function below 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

Here's how it would look like with accumulator:

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

In this case, score is the accumulator, which starts as 0. We also have an index (also starting as 0) that keeps track of which position in the string to grab. The base case, when we reach the end of either string, is to return the accumulated score so far.

Answer 2

Just wanted to make an variant of Chris' answer that uses lists of chars:

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

No use stopping there. Since this now have become list iteration we can use higher order procedure. Typically we want a fold-left or foldl and SRFI-1 fold is an implementation of that that doesn't require the lists to be of the same length:

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

If you accumulating and the order doesn't matter always choose a left fold since it's always tail recursive in Scheme.