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;
if (addLetter < res)
  res = addLetter;
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;

  • Adding a letter
  • 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.

  • $\begingroup$ What formula does your assignment ask for? $\endgroup$ – Yuval Filmus Jan 25 '17 at 14:36
  • $\begingroup$ None specific, it literally just says "Formulate this recursion using mathematical notation".. $\endgroup$ – Nyfiken Gul Jan 25 '17 at 14:38
  • 1
    $\begingroup$ *shrug* It seems like you should be asking for clarification from whoever set this to you, not from us. $\endgroup$ – David Richerby Jan 25 '17 at 14:51
  • $\begingroup$ 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 $\endgroup$ – Nyfiken Gul Jan 25 '17 at 15:04
  • $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ Okay, thanks a lot. So the sigma's would be the words lengths? Am I understand you correctly then? Because I don't think we have to consider any corner cases where the length exceeds the word and so forth. Okay, do you have any examples just for a hint? Thanks a bunch for the help, I'm just really struggling with this as I haven't done anything like it before. $\endgroup$ – Nyfiken Gul Jan 25 '17 at 14:48
  • $\begingroup$ 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). $\endgroup$ – Yuval Filmus Jan 25 '17 at 14:51
  • $\begingroup$ Oh, I see - thank you so much! So I would then write the recursion as a function of the individual symbols of the two words? That might be easier, but I'm still not really sure how to formulate it $\endgroup$ – Nyfiken Gul Jan 25 '17 at 15:03
  • $\begingroup$ You can choose any of the two possibilities I mention. Perhaps the second is indeed easier. Unfortunately I will not provide any details beyond this. $\endgroup$ – Yuval Filmus Jan 25 '17 at 15:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.