levenshtein_distance_rec.sf

#!/usr/bin/ruby

#
## https://rosettacode.org/wiki/Levenshtein_distance
#

func lev(s, t) is cached {

    s.is_empty && return t.len;
    t.is_empty && return s.len;

    var s1 = s.slice(1);
    var t1 = t.slice(1);

    s[0] == t[0] ? __FUNC__(s1, t1)
                 : 1+[
                        __FUNC__(s1, t1),
                        __FUNC__(s,  t1),
                        __FUNC__(s1, t )
                     ].min;
}

say lev(%c'kitten', %c'sitting');               # prints: 3
say lev(%c'rosettacode', %c'raisethysword');    # prints: 8