# Formulating a recursion using mathematical notation [closed]

So I'm assigned a task that involves formulating a quite complex recursion of several variables using 'mathematical notation'. The assignment is quite sparse when it comes to additional information, but below is the code anyway;

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


}

The method calculates the amount of the following operations it takes to get from String w1 to w2 and vice-versa;

• Removing a letter
• Change an already exisiting letter

I'm not really sure where to proceed from there. I've managed to write something along the lines of a mathematic formula with conditionals but it just looks really messy and with a lot of hand-written conditions.

• What formula does your assignment ask for? – Yuval Filmus Jan 25 '17 at 14:36
• None specific, it literally just says "Formulate this recursion using mathematical notation".. – Nyfiken Gul Jan 25 '17 at 14:38
• *shrug* It seems like you should be asking for clarification from whoever set this to you, not from us. – David Richerby Jan 25 '17 at 14:51
• Yea I guess so, just hoped it was some established concept that I just needed to wrap my head around - sorry for the stupid question – Nyfiken Gul Jan 25 '17 at 15:04
• What exactly is your question? I don't see a question in your post, just a bunch of statements. This is a question-and-answer site, so it's important to articulate a specific question. Can you edit accordingly? Also, coding questions are generally off-topic here, and not everyone here necessarily knows Java, so some members of the community might judge the question to be off-topic -- we'll see. Finally, can you edit to fix the formatting? The indentation of your code doesn't look right. – D.W. Jan 25 '17 at 16:49

Abbreviating partDist to $D$, you are looking for a formula for $D(w_1,w_2)$. Given the form of the recursion, it will be easier to state a formula for $D(x_1\sigma_1,x_2\sigma_2)$, where $\sigma_1,\sigma_2$ are symbols (i.e., characters) and $x_1,x_2$ are strings; additional base cases will cover the cases in which $w_i$ cannot be decomposed as $x_i\sigma_i$. The formula will be a minimum of two or three terms, depending on whether $\sigma_1 = \sigma_2$ or not.
Alternatively, you can write a recursion for $$D(x_1x_2\ldots x_n,y_1y_2\ldots y_m).$$ Here the base cases would be $n=0$ and $m=0$, and in the recursive case you will have to distinguish between $x_n = y_m$ and $x_n \leq y_m$. Here all the $x_i$ and $y_j$ are symbols.
• No, the $\sigma$s will be individual symbols. You don't need the lengths at all in the recursion. The symbol $\sigma_1$ corresponds to the mouthful w1.charAt(w1len - 1). – Yuval Filmus Jan 25 '17 at 14:51