Advice converting recursive Diff Algorithm to an iterative one?

Greetings!

I wrote a recursive diff algorithm from scratch. It finds the "best match" between two strings such that the differences are minimized, and prints out the two strings with any differences represented in CAPS. It works fine "as is", except that it is pretty inefficient. I've been staring at it for a day and a half now, trying to find ways to make it iterative or at least reduce the stack depth that it reaches, but I'm at my wit's end and was hoping that a keen mind here would see the solution more clearly than me.

Below is the meat of the code. The MergePoint class that is referenced is just a simple "linked list" style node that contains an "index in original" integer, an "index in altered" integer, and a "next" MergePoint. The MergePoint list represents a series of indexes in each array that have been "merged". When the chain is completed, any indexes that are not represented in the chain are insertions/deletions. The NullObject object is an extension of MergePoint that, thinking back on it, wasn't strictly necessary to create and can basically be considered a regular 'null'.

Any advice/suggestions would be very deeply appreciated.

public class StringCompare 
{
    public static int[][]       mergeList       = new int[0][0];
    public static MergePoint    NULL            = NullObject.getNull();
    public static int           maxMerged       = 0;
    public static int           minClusterSize  = -1;

    public static void diff(String orig, String alt)
    {
        String[] original = orig.toUpperCase().split(" ");
        String[] altered  = alt.toUpperCase().split(" ");

        for(int i = 0; i < altered.length; i++)
        {
            merge(original, altered, 0, i, NULL, NULL, 0, 0);
        }


        for(int i = 0; i < mergeList.length; i++)
        {
            or[mergeList[i][0]] = or[mergeList[i][0]].toLowerCase();
            al[mergeList[i][1]] = al[mergeList[i][1]].toLowerCase();
        }

        printStringArray(or);
        printStringArray(al);
    }

    private void printStringArray(String[] arr)
    {
        for(String word : arr)
        {
            System.out.print(word.trim() + " ");
        }

        System.out.println();
    }

    private static void merge(String[] original, String[] altered, int indexInOriginal, int indexInAltered, MergePoint head, MergePoint tail, int listSize, int clusters)
    {
        if (indexInOriginal >= original.length)
        {           
            if (listSize > 0)
            {
                if (((listSize == maxMerged) && (clusters < minClusterSize)) ||
                    (listSize > maxMerged))
                {
                    storeMergePoints(head, listSize, clusters);
                }
            }
        }
        else if (indexInAltered >= altered.length)
        {
            if (tail != NULL)
            {
                merge(original, altered, (indexInOriginal + 1), (tail.indexInNew() + 1), head, tail, listSize, clusters);
            }
            else
            {
                merge(original, altered, (indexInOriginal + 1), 0, head, tail, listSize, 0);
            }
        }
        else
        {
            if(original[indexInOriginal].equals(altered[indexInAltered]))
            {
                MergePoint  mergePoint  = new MergePoint(indexInOriginal, indexInAltered);
                MergePoint  bookMark    = NULL;             
                int         newClusters = clusters;

                if (indexInOriginal != (tail.indexInOriginal() + 1))
                {
                    newClusters++;
                }

                if (indexInAltered != (tail.indexInNew() + 1))
                {
                    newClusters++;
                }

                if (head == NULL)
                {
                    head = mergePoint;
                    tail = head;
                }
                else
                {
                    tail.setNext(mergePoint);

                    bookMark开发者_如何学Python    = tail;                 
                    tail        = tail.next();
                }

                merge(original, altered, (indexInOriginal + 1), (indexInAltered + 1), head, tail, (listSize + 1), newClusters);

                if (bookMark == NULL)
                {
                    merge(original, altered, indexInOriginal, (indexInAltered + 1), NULL, NULL, 0, 0);
                }
                else
                {
                    bookMark.setNext(NULL);

                    merge(original, altered, indexInOriginal, (indexInAltered + 1), head, bookMark, listSize, newClusters);
                }
            }
            else
            {
                merge(original, altered, indexInOriginal, (indexInAltered + 1), head, tail, listSize, clusters);
            }
        }
    }

    public static void storeMergePoints(MergePoint current, int size, int clusters)
    {       
        mergeList       = new int[size][2];
        maxMerged       = size;
        minClusterSize  = clusters;

        for(int i = 0; i < size; i++)
        {
            mergeList[i][0] = current.indexInOriginal();
            mergeList[i][1] = current.indexInNew();
            current         = current.next();
        }       
    }
}

---

For replacing recursion with iteration you may consider replacing the JVM stack with a stack object that you control: java.util.Stack would be quite suitable for this. Simply push() and pop() your data on that stack on each iteration instead of having the method call itself.