I'm having some trouble understanding part of Skienna's algorithm for edit distance presented in his Algorithm Design Manual. I'm posting the recursive version, prior to when he applies dynamic programming to the problem, but my question still stands in that version too I think.He provides the following code:#define MATCH       0#define INSERT      1#define DELETE      2int match(char c, char d){    if (c == d) return(0);    else return(1);}int indel(char c){    return(1);}int string_compare(char *s, char *t, int i, int j){        int k;                  /* counter */        int opt[3];             /* cost of the three options */        int lowest_cost;        /* lowest cost */        if (i == 0) return(j * indel(' '));        if (j == 0) return(i * indel(' '));        opt[MATCH] = string_compare(s,t,i-1,j-1) + match(s[i],t[j]);        opt[INSERT] = string_compare(s,t,i,j-1) + indel(t[j]);        opt[DELETE] = string_compare(s,t,i-1,j) + indel(s[i]);        lowest_cost = opt[MATCH];        for (k=INSERT; k<=DELETE; k++)                if (opt[k] < lowest_cost) lowest_cost = opt[k];        return( lowest_cost );}I am having trouble understanding the logic behind how the indices are decremented when arriving at opt[INSERT] and opt[DELETE]. They seem backwards to me. How can I prove to myself that they are correct?
Skienna's recursive algorithm for edit distance
algorithms;edit distance
The two strings s and t are compared starting from the high index,down to index 1. This is not visible since the initial call tostring_compare is not provided. The i and j arguments for thatinitial call are the length of strings s and t.It should be noted that s and t could be globals, since they arethe same in all calls.A call to the function string_compare(s,t,i,j) is intended tocompute the minimum edit distance of the prefixes s[1..i] and t[1..j].It first compares the two strings at indices i and j, and therecursively at lower indices.It always tries 3 ways of finding the shortest distance:by assuming there was a match or a susbstitution edit depending onwhether s[i]==t[j];by assuming there is an insertion edit of t[j];by assuming there is an deletion edit of s[i];Then it computes recursively the sortest distance for the rest of bothstrings, and adds 1 to that result, when there is an edit on this call.When s[i]==t[j] the two strings match on these indices. Hence thecorresponding indices are both decremented, to recursively compute theshortest distance of the prefixes s[1..i-1] and t[1..j-1]. Aproper match does not increase the distance. Hencedist(s[1..i],t[1..j])= dist(s[1..i-1], t[1..j-1]).When s[i]=/=t[j] the two strings do not match, but can be made tomatch by a substitution edit. Hence the same recursive call ispossible, but the resulting shortest distance must be incremented byone for the substitution edit. Hence dist(s[1..i],t[1..j])=dist(s[1..i-1], t[1..j-1])+1.That is why the function match returns 0 when there is a match, and1 when there is none.Another possibility is not to try for a match, but assume that t[j]is due to an insertion edit in the case of the smallest distance.Hence that inserted symbol is ignored by replacing t[1..j] byt[1..j-1], ie by computing the shortest distance of s[1..i] andt[1..j-1], which is string_compare(s,t,i,j-1), and then adding 1for the insertion edit.The next and last try is the symmetric one, when one assume that thesymbol s[i] was deleted, and thus does not have to appear in t.The results of the 3 attempts are strored in the array opt, and thesmallest value of the 3 is kept as shortest distance for s[1..i] andt[1..j].The decrementations of indices is either because the correspondingstring elements match, or because they have been taken into account byan edit operation.