>you never NEED recursion
I would agree. My only point is that recursion can vastly simplify some algorithms.
>The K-approximation I'd need more details on...
A K-approximation returns the minimum character differences between two strings. For example, how many character differences between the two following strings:
s1 : 'Hello World'
s2 : 'Hallo World'
Answer 1. Easy. Now how many character differences between:
s1 : 'Hello World'
s2 : Hllo World'
Answer 1: Missing character in s2. How many differences now:
s1: 'Hello World'
s2: 'Hxallo World'
Answer 2: Extra character in s2 + 1 incorrect character.
I would love to see a relatively straight forward way of doing this without recursion. For the record, here's my algorithm which uses AnsiString. AnsiString is references from index 1, not zero like c strings. For most intents, AnsiString is equivelent to STL string class.
Code:
int LinguaLex::kRecurse(const AnsiString& s1, const AnsiString& s2, int k, int maxK)
{
// K-Approximation string comparison (case sensitive)
if (s1 == s2) return 0;
if (k >= maxK && maxK > -1) return maxK;
int lmax;
int lmin;
int len1 = s1.Length();
int len2 = s2.Length();
if (len1 > len2)
{
lmax = len1;
lmin = len2;
}
else
{
lmax = len2;
lmin = len1;
}
for(int n = 1; n <= lmin; n++)
{
if (s1[n] != s2[n])
{
// Recursive call to find min difference
AnsiString sub1(s1.SubString(n+1, len1 - n));
AnsiString sub2(s2.SubString(n+1, len2 - n));
if (lmax < maxK || maxK == -1) maxK = lmax;
int xc = kRecurse(sub1, sub2, k+1, maxK);
int mc = kRecurse(s1.SubString(n, len1 - n + 1), sub2, k+1, xc + 1);
int ac;
if (xc < mc)
ac = kRecurse(sub1, s2.SubString(n, len2 - n + 1), k+1, xc + 1);
else
ac = kRecurse(sub1, s2.SubString(n, len2 - n + 1), k+1, mc + 1);
if (xc <= mc && xc <= ac)
return xc + 1;
else
if (mc <= xc && mc <= ac)
return mc + 1;
else
if (ac <= xc && ac <= mc)
return ac + 1;
}
}
return lmax - lmin;
}