可视化递归
Visualising recursion
我正在尝试跟踪合并排序中的递归 'happens' 如何从堆栈中压入和弹出值。我可以理解该算法是如何工作的，并且可以按照纸上的步骤进行操作，但是很难想象什么以及何时推送和弹出值。我的合并排序代码，固定为 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，依此类推，然后呢？这些值是如何递归合并的？
有许多非常有用的网站可用于可视化排序算法。这个将引导您逐步完成排序和代码。
http://visualgo.net/sorting.html#
其他：
[1] http://www.sorting-algorithms.com/ 常用排序比较、Big O 复杂度、可视化等
[2] https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html 很好的可视化，没有解释
[3]http://sorting.at/很漂亮，不解释
跟踪递归是一件很有用的事情。
其他答案之一 点 你对其他人所做的一些可视化。
我认为您将受益于能够将您自己的跟踪添加到您自己的代码中。考虑到这一点，请考虑以下代码：
我发现有两个有用的东西是添加深度计数器和标签，这样您就可以在 "context" 中看到每个调用。
这是当前输出的样子 - 我考虑过将跟踪信息添加到 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.
}
}
我正在尝试跟踪合并排序中的递归 'happens' 如何从堆栈中压入和弹出值。我可以理解该算法是如何工作的，并且可以按照纸上的步骤进行操作，但是很难想象什么以及何时推送和弹出值。我的合并排序代码，固定为 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，依此类推，然后呢？这些值是如何递归合并的？
有许多非常有用的网站可用于可视化排序算法。这个将引导您逐步完成排序和代码。
http://visualgo.net/sorting.html#
其他：
[1] http://www.sorting-algorithms.com/ 常用排序比较、Big O 复杂度、可视化等
[2] https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html 很好的可视化，没有解释
[3]http://sorting.at/很漂亮，不解释
跟踪递归是一件很有用的事情。
其他答案之一 点 你对其他人所做的一些可视化。
我认为您将受益于能够将您自己的跟踪添加到您自己的代码中。考虑到这一点，请考虑以下代码：
我发现有两个有用的东西是添加深度计数器和标签，这样您就可以在 "context" 中看到每个调用。 这是当前输出的样子 - 我考虑过将跟踪信息添加到 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.
}
}