java - 可视化递归

Question

我试图通过从堆栈中放入和弹出值来跟踪合并排序中递归是如何“发生”的。我可以理解该算法是如何工作的，并且可以按照纸上的步骤进行操作，但很难想象出什么值以及何时推送和弹出值。我的合并排序代码针对 5,4,3,2,1,0 的简单数组进行了修复，如下:

public class MergeSort {

private static int[] ar = new int[6];

    public static void main(String[] args) throws Exception {
        MergeSort s=new MergeSort();   
        ar[0]=5;ar[1]=4;ar[2]=3;ar[3]=2;ar[4]=1;ar[5]=0;
        s.mergesort(ar);
    }


        static int[] mergesort(int[] arr){
        printArray(arr);
        System.out.println(" ");

        int size=arr.length;

        if(size == 1){

            return arr;
        }

        else{

           int[] ar1=new int[size/2];
           int[] ar2=new int[size-ar1.length];
           System.arraycopy(arr, 0, ar1, 0, ar1.length);
           System.arraycopy(arr, ar1.length, ar2, 0, ar2.length);
           mergesort(ar1);
           mergesort(ar2);
           merge(ar1,ar2,arr);
           return arr;

        }

    }

    static int[] merge(int[] ar1,int[] ar2,int[] temp){


        int pointer1=0;
        int pointer2=0;
        int pointer3=0;
       while(pointer1 < ar1.length && pointer2 < ar2.length){
           if(ar1[pointer1] < ar2[pointer2]){
               temp[pointer3]=ar1[pointer1];

               pointer1++;
           }

           else{
               temp[pointer3] = ar2[pointer2];
               pointer2++;
           }
           pointer3++;
       }


        System.arraycopy(ar1, pointer1, temp, pointer3, ar1.length - pointer1);
        System.arraycopy(ar2, pointer2, temp, pointer3, ar2.length - pointer2);


      return temp;
    }


}

并产生输出:

5 4 3 2 1 0  
5 4 3  
5  
4 3  
4  
3  
2 1 0  
2  
1 0  
1  
0

正如预期的那样，该函数将 543 压入堆栈，然后压入 5，然后压入 4 和 3，依此类推，然后呢？值是如何递归合并的？

Answer 1

跟踪递归是一件很有用的事情。

其他答案之一指出其他人已经完成的一些可视化。

我认为您将受益于能够将您自己的跟踪添加到您自己的代码中。考虑到这一点，请考虑以下代码:

我发现有两件事很有帮助，那就是添加深度计数器和标签，这样您就可以在“上下文”中看到每个调用。这是当前输出的样子 - 我曾考虑过向 merge() 添加跟踪信息，但认为这将是一个有用的说明。

诀窍是修改 printArray() 以根据当前深度缩进。添加一个仅转储字符串的“tracePrint() 也很简单；我起诉了 printArray()，因为这就是代码所使用的。

还要注意 >mergsort() 和 < 表示进入和退出的标记方法的约定。

请注意，输出更加详细，对于我正在编写的代码，我不会使用所有这些对 printArray() 的调用，但我希望您发现它很有趣，并希望它可以帮助您解决将来的递归问题。快乐编码:-)

输出示例

$ java MergeSort 
>mergesort len=6 [ 5, 4, 3, 2, 1, 0 ]
|   >mergesort:ar1 len=3 [ 5, 4, 3 ]
|   |   >mergesort:ar1:ar1 len=1 [ 5 ]
|   |   <mergesort:ar1:ar1 len=1 [ 5 ]
|   |   >mergesort:ar1:ar2 len=2 [ 4, 3 ]
|   |   |   >mergesort:ar1:ar2:ar1 len=1 [ 4 ]
|   |   |   <mergesort:ar1:ar2:ar1 len=1 [ 4 ]
|   |   |   >mergesort:ar1:ar2:ar2 len=1 [ 3 ]
|   |   |   <mergesort:ar1:ar2:ar2 len=1 [ 3 ]
|   |   >merge:ar1      len=1 [ 4 ]
|   |    merge:ar2      len=1 [ 3 ]
|   |    merge:temp     len=2 [ 4, 3 ]
|   |    temp.afterWhile len=2 [ 3, 3 ]
|   |    temp.acopyAR1  len=2 [ 3, 4 ]
|   |   <merge.acopyAR2  len=2 [ 3, 4 ]
|   |   <mergesort:ar1:ar2 len=2 [ 3, 4 ]
|   >merge:ar1      len=1 [ 5 ]
|    merge:ar2      len=2 [ 3, 4 ]
|    merge:temp     len=3 [ 5, 4, 3 ]
|    temp.afterWhile len=3 [ 3, 4, 3 ]
|    temp.acopyAR1  len=3 [ 3, 4, 5 ]
|   <merge.acopyAR2  len=3 [ 3, 4, 5 ]
|   <mergesort:ar1 len=3 [ 3, 4, 5 ]
|   >mergesort:ar2 len=3 [ 2, 1, 0 ]
|   |   >mergesort:ar2:ar1 len=1 [ 2 ]
|   |   <mergesort:ar2:ar1 len=1 [ 2 ]
|   |   >mergesort:ar2:ar2 len=2 [ 1, 0 ]
|   |   |   >mergesort:ar2:ar2:ar1 len=1 [ 1 ]
|   |   |   <mergesort:ar2:ar2:ar1 len=1 [ 1 ]
|   |   |   >mergesort:ar2:ar2:ar2 len=1 [ 0 ]
|   |   |   <mergesort:ar2:ar2:ar2 len=1 [ 0 ]
|   |   >merge:ar1      len=1 [ 1 ]
|   |    merge:ar2      len=1 [ 0 ]
|   |    merge:temp     len=2 [ 1, 0 ]
|   |    temp.afterWhile len=2 [ 0, 0 ]
|   |    temp.acopyAR1  len=2 [ 0, 1 ]
|   |   <merge.acopyAR2  len=2 [ 0, 1 ]
|   |   <mergesort:ar2:ar2 len=2 [ 0, 1 ]
|   >merge:ar1      len=1 [ 2 ]
|    merge:ar2      len=2 [ 0, 1 ]
|    merge:temp     len=3 [ 2, 1, 0 ]
|    temp.afterWhile len=3 [ 0, 1, 0 ]
|    temp.acopyAR1  len=3 [ 0, 1, 2 ]
|   <merge.acopyAR2  len=3 [ 0, 1, 2 ]
|   <mergesort:ar2 len=3 [ 0, 1, 2 ]
>merge:ar1      len=3 [ 3, 4, 5 ]
 merge:ar2      len=3 [ 0, 1, 2 ]
 merge:temp     len=6 [ 5, 4, 3, 2, 1, 0 ]
 temp.afterWhile len=6 [ 0, 1, 2, 2, 1, 0 ]
 temp.acopyAR1  len=6 [ 0, 1, 2, 3, 4, 5 ]
<merge.acopyAR2  len=6 [ 0, 1, 2, 3, 4, 5 ]
<mergesort len=6 [ 0, 1, 2, 3, 4, 5 ]
$ 

MergeSort.java

public class MergeSort {

    private static int[] ar = new int[6];

    public static void main(String[] args) throws Exception {
        ar[0]=5;ar[1]=4;ar[2]=3;ar[3]=2;ar[4]=1;ar[5]=0;
        // note: could also do this:
        // ar = = new int[6] { 5, 4, 3, 2, 1, 0 };


        MergeSort s=new MergeSort();
        s.mergesort(0, "", ar);

        // fwiw... all of the methods and members (well, just 'ar')
        // are static so the following is equivalent to the above.
        //    MergeSort.mergesort( 0, "", ar );
    }

    // added: depth & label to provide context for recursion.
    static int[] mergesort(int depth, String label, int[] arr){
        printArray(depth, ">mergesort"+label, arr);
        //System.out.println(" ");

        int size=arr.length;

        if(size >= 2) {
           int[] ar1=new int[size/2];
           int[] ar2=new int[size-ar1.length];
           System.arraycopy(arr, 0, ar1, 0, ar1.length);
           System.arraycopy(arr, ar1.length, ar2, 0, ar2.length);
           // note that we're appending labels so all subsequent
           // calls to mergesort() will have their 'lineage' baked
           // into the label.
           mergesort( 1+depth, label+":ar1", ar1);
           mergesort( 1+depth, label+":ar2", ar2);
           merge(depth, ar1, ar2, arr);
        }
        printArray(depth, "<mergesort"+label, arr);
        return arr; // single return point.
    }

    // added: depth & label aren't so useful here, but just for fun.
    static int[] merge(int depth, int[] ar1,int[] ar2,int[] temp){
       // note: tweaked spacing here to make these line up "nicely"
       // with the longer labels below, like "temp.afterWHile".
       // (output looks better, here just looks messy).
       printArray( depth, ">merge:ar1     ", ar1 );
       printArray( depth, " merge:ar2     ", ar2 );
       printArray( depth, " merge:temp    ", temp );

       int pointer1=0;
       int pointer2=0;
       int pointer3=0;
       while(pointer1 < ar1.length && pointer2 < ar2.length){
          if(ar1[pointer1] < ar2[pointer2]){
             temp[pointer3]=ar1[pointer1];
             pointer1++;
          }
          else{
             temp[pointer3] = ar2[pointer2];
             pointer2++;
          }
          pointer3++;
       }
       printArray( depth, " temp.afterWhile", temp );
       System.arraycopy(ar1, pointer1, temp, pointer3, ar1.length - pointer1);
       printArray( depth, " temp.acopyAR1 ", temp );
       System.arraycopy(ar2, pointer2, temp, pointer3, ar2.length - pointer2);
       printArray( depth, "<merge.acopyAR2 ", temp );
       return temp;
    }

    // wrote a simple printArray() that uses depth & label.
    static void printArray( int depth, String label, int[] array ) {
       for( int i = 0; i < depth; ++i ) {
          System.out.print("|   "); // indent to depth.
       }
       System.out.print( label );
       System.out.print( " len="+array.length+" [ " );
       String delim = "";
       for( int i = 0; i < array.length; ++i ) {
          System.out.print( delim + array[i] );
          delim = ", ";
       }
       System.out.println( " ]"); // end the line we just created.
    }
}