Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have this recursive function, written in Java. Assignment is to translate it to mathematical notation.

int dist(String w1, String w2, int w1len, int w2len) {
    if (w1len == 0) return w2len;
    if (w2len == 0) return w1len;
    int res = dist(w1, w2, w1len - 1, w2len - 1) + (w1.charAt(w1len - 1) == w2.charAt(w2len - 1) ? 0 : 1);      
    int addLetter = dist(w1, w2, w1len - 1, w2len) + 1;
    if (addLetter < res)
        res = addLetter;
    int deleteLetter = dist(w1, w2, w1len, w2len - 1) + 1;
    if (deleteLetter < res)
        res = deleteLetter;
    return res;
}

My attempt, is this valid?

$del = f(u,v,m,n-1)+1\\add = f(u,v,m-1,n)+1\\res = f(u,v,m-1,n-1)$

$f(u,v,m,n)=\begin{cases} n & m=0\\ m & n=0\\ MIN(del,MIN(add,res)) & u_{m-1}=v_{n-1}\\ MIN(del,MIN(add,res+1)) & u_{m-1}\neq v_{n-1} \end{cases}$

share|improve this question
    
So, $u$ and $v$ are strings? In mathematics we probably would not consider $0$ to be a string, so $u=0$ would not occur. –  GEdgar Sep 20 '12 at 1:10
    
@GEdgar Oops, mixed up the variables. Yes $u$ and $v$ are strings, but they are never returned, only $m$ and $n$. I updated my question –  hamohl Sep 20 '12 at 1:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.