There are many problems that are really hard or impossible
to solve without recursion. For example chess search
or the edit distance problem. To really understand I think
you have to study proof by induction.
Here's an example of code to solve the edit distance problem
www.cs.wisc.edu/~condon/cs577/homeworks/ph4.ps
The algorithm works or at least appears to work because
take for example algorithm => altruistic
If the best operation is to copy then
we have cost(copy) + mincost(lgorithm=>ltruistic)
All of the operations show this structure with modification.
Thus a algorithm can be developed that solves
min ( cost(copy) + mincost(lgorithm=>ltruistic)
cost(replace) + mincost(lgorithm=>altruistic)
cost(insert) + mincost(algorithm=>ltruistic)
and so on for the rest of the operations )
The problem is a strictly recursive solution is too slow so
we save subproblems in a table.
Code:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define EDIT_INFINITY 100000
#define OP_COPY 0
#define OP_REPLACE 1
#define OP_DELETE 2
#define OP_INSERT 3
#define OP_TWIDDLE 4
#define OP_KILL 5
static const int cost[] = {1, 4, 2, 3, 1, 0};
struct EditSequence
{
int cost;
vector<int> op;
};
#define MAX_M 100
#define MAX_N 100
EditSequence minCostTbl[MAX_M + 3][MAX_N + 3];
EditSequence minCost(string x, string y, int i, int j)
{
int m = x.length();
int n = y.length();
if (i == m + 1 && j == n)
{
EditSequence s;
s.cost = 0;
return s;
}
if (i > m || j > n)
{
EditSequence s;
s.cost = EDIT_INFINITY;
return s;
}
EditSequence s = minCostTbl[i][j];
if (s.cost != -1)
return s;
EditSequence t1 = minCost(x, y, i + 1, j + 1);
EditSequence t2 = minCost(x, y, i + 1, j);
EditSequence t3 = minCost(x, y, i, j + 1);
EditSequence t4 = minCost(x, y, i + 2, j + 2);
EditSequence t5 = minCost(x, y, m + 1, j);
int mc = EDIT_INFINITY;
int mo = OP_INSERT;
EditSequence* sequence = 0;
int c;
if (i < m && j < n && x[i] == y[j])
{
c = cost[OP_COPY] + t1.cost;
if (c < mc)
{
mc = c;
mo = OP_COPY;
sequence = &t1;
}
}
c = cost[OP_REPLACE] + t1.cost;
if (c < mc)
{
mc = c;
mo = OP_REPLACE;
sequence = &t1;
}
c = cost[OP_DELETE] + t2.cost;
if (c < mc)
{
mc = c;
mo = OP_DELETE;
sequence = &t2;
}
c = cost[OP_INSERT] + t3.cost;
if (c < mc)
{
mc = c;
mo = OP_INSERT;
sequence = &t3;
}
if (i + 1 < m && j + 1 < n
&& x[i + 1] == y[j] && x[i] == y[j + 1])
{
c = cost[OP_TWIDDLE] + t4.cost;
if (c < mc)
{
mc = c;
mo = OP_TWIDDLE;
sequence = &t4;
}
}
c = cost[OP_KILL] + t5.cost;
if (c < mc)
{
mc = c;
mo = OP_KILL;
sequence = &t5;
}
sequence->cost = mc;
sequence->op.push_back(mo);
minCostTbl[i][j] = *sequence;
return *sequence;
}
EditSequence minCost(string x, string y)
{
return minCost(x, y, 0, 0);
}
void printSequence(const EditSequence& s)
{
cout << "min cost = " << s.cost << endl;
for (int i = s.op.size() - 1; i >= 0; --i)
{
switch(s.op[i]) {
case OP_COPY:
cout << "copy" << endl;
break;
case OP_REPLACE:
cout << "replace" << endl;
break;
case OP_DELETE:
cout << "delete" << endl;
break;
case OP_INSERT:
cout << "insert" << endl;
break;
case OP_TWIDDLE:
cout << "twiddle" << endl;
break;
case OP_KILL:
cout << "kill" << endl;
break;
default:
cout << "error" << endl;
break;
}
}
}
int main(int argc, char *argv[])
{
char *x, *y;
if (argc != 3) {
cout << "error: invalid number of arguments" << endl;
return -1;
}
x = argv[1];
y = argv[2];
EditSequence invalidSequence;
invalidSequence.cost = -1;
for (int i = 0; i < MAX_M + 3; ++i) {
for (int j = 0; j < MAX_N + 3; ++j) {
minCostTbl[i][j] = invalidSequence;
}
}
EditSequence s = minCost(x, y);
printSequence(s);
return 0;
}