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

Sylwester · Accepted Answer · 2014-03-31 17:26:49Z

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.

You might want to add that the SRFI/1 reference implementation of fold is indeed tail-recursive (see srfi.schemers.org/srfi-1/srfi-1-reference.scm).
@uselpa A left fold would always be. Many implementations provide their own SRFI-1 that is tail recursive all the way. A TRMCO-ed map performs much better than in the reference implementation.
Why stop at fold? You can use string-fold from SRFI 13, and skip the string->list steps. ;-)
@ChrisJester-Young string-fold doesn't take more than one string argument so you cannot use it the same way.
@Sylwester Quick, file a bug report! (Seriously though, I can understand why having more than one string is troublesome, because of the need to also be able to optionally supply start/end parameters. Still, bummer.)

C. K. Young · Accepted Answer · 2014-03-31 14:35:02Z

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.

Thank you so much:) I think I now grasp the concept. Your code makes perfect sense. Thanks again :)

Collectives™ on Stack Overflow

Recursion Vs. Tail Recursion

2 Answers 2

5 Comments

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

1 Comment

Related