Are there any examples of mutual recursion? (original) (raw)

Top down merge sort can use a pair of mutually recursive functions to alternate the direction of merge based on level of recursion.

For the example code below, a[] is the array to be sorted, b[] is a temporary working array. For a naive implementation of merge sort, each merge operation copies data from a[] to b[], then merges b[] back to a[], or it merges from a[] to b[], then copies from b[] back to a[]. This requires n · ceiling(log2(n)) copy operations. To eliminate the copy operations used for merging, the direction of merge can be alternated based on level of recursion, merge from a[] to b[], merge from b[] to a[], ..., and switch to in place insertion sort for small runs in a[], as insertion sort on small runs is faster than merge sort.

In this example, MergeSortAtoA() and MergeSortAtoB() are the mutually recursive functions.

Example java code:

    static final int ISZ = 64;              // use insertion sort if size <= ISZ

    static void MergeSort(int a[])
    {
        int n = a.length;
        if(n < 2)
            return;
        int [] b = new int[n];
        MergeSortAtoA(a, b, 0, n);
    }
    
    static void MergeSortAtoA(int a[], int b[], int ll, int ee)
    {
        if ((ee - ll) <= ISZ){              // use insertion sort on small runs
            InsertionSort(a, ll, ee);
            return;
        }
        int rr = (ll + ee)>>1;              // midpoint, start of right half
        MergeSortAtoB(a, b, ll, rr);
        MergeSortAtoB(a, b, rr, ee);
        Merge(b, a, ll, rr, ee);            // merge b to a
    }
    
    static void MergeSortAtoB(int a[], int b[], int ll, int ee)
    {
        int rr = (ll + ee)>>1;              // midpoint, start of right half
        MergeSortAtoA(a, b, ll, rr);
        MergeSortAtoA(a, b, rr, ee);
        Merge(a, b, ll, rr, ee);            // merge a to b
    }
    
    static void Merge(int a[], int b[], int ll, int rr, int ee)
    {
        int o = ll;                         // b[]       index
        int l = ll;                         // a[] left  index
        int r = rr;                         // a[] right index
    
        while(true){                        // merge data
            if(a[l] <= a[r]){               // if a[l] <= a[r]
                b[o++] = a[l++];            //   copy a[l]
                if(l < rr)                  //   if not end of left run
                    continue;               //     continue (back to while)
                while(r < ee){              //   else copy rest of right run
                    b[o++] = a[r++];
                }
                break;                      //     and return
            } else {                        // else a[l] > a[r]
                b[o++] = a[r++];            //   copy a[r]
                if(r < ee)                  //   if not end of right run
                    continue;               //     continue (back to while)
                while(l < rr){              //   else copy rest of left run
                    b[o++] = a[l++];
                }
                break;                      //     and return
            }
        }
    }

    static void InsertionSort(int a[], int ll, int ee)
    {
        int i, j;
        int t;
        for (j = ll + 1; j < ee; j++) {
            t = a[j];
            i = j-1;
            while(i >= ll && a[i] > t){
                a[i+1] = a[i];
                i--;
            }
            a[i+1] = t;
        }   
    }