递归执行顺序的探究

1 问题描述
最近两天在思考如何使用蛮力法解决旅行商问题(此问题,说白了就是如何求解n个不同字母的所有不同排序的序列问题,即共有n!次不同排序)。

为此,我认真看了一篇出自CSDN上的博客文章,其中有一段核心代码就是在for循环里面添加一句递归调用语句,来实现n!次排序。因此,我对文章中的那段核心代码苦苦不得其解——其执行顺序究竟是咋样的呢?

附其简要代码:

public int count = 0;
public  void Arrange(int[] A,int start,int step,int n,int Max){
        if(step == 2)
            System.out.println("第"+(++count)+"次走完一圈");
        if(count == Max)
            System.out.println("已完成!!!");
        else{
            for(int i = start;i < n;i++){
                swapArray(A,start,i);
                Arrange(A,start+1,step+1,n,Max);
                swapArray(A,i,start);
            }
        }
    }

2 解决方案
2.1 问题化简

刚开始学习递归时,课本上都会给出使用递归实现斐波那契数问题(PS:f(1) = 1,f(2) = 1,f(3) = 2,f(4) = 3,…,f(n) = f(n-1) + f(n-2),求解f(n)),那我们就先来探讨使用递归法求解第n个斐波那契数的具体执行顺序:

package com.liuzhen.chapterThree;

public class Test {
    public int Fibonacci(int n){
        System.out.println("第"+n+"次递归,结果:");
        if(n == 1 || n == 2)
            return 1;
        System.out.println("********");
        return Fibonacci(n-1) + Fibonacci(n-2);
    } 
    
    public static void main(String[] args){
        Test temp = new Test();
        System.out.println("运行结果:"+temp.Fibonacci(4));
    }
}

运行结果:

第4次递归,结果:
********
第3次递归,结果:
********
第2次递归,结果:
第1次递归,结果:
第2次递归,结果:
第4次递归,结果:
********
第3次递归,结果:
********
第2次递归,结果:
第1次递归,结果:
第2次递归,结果:
运行结果:3

此处是求解第4个斐波那契数,看到运行结果依次输出数字4,3,2,1,2,4,3,2,1,2。可以看到,输出的数字按照第一遍输出的样式重复输出了一次。

此处递归语句:return Fibonacci(n-1) + Fibonacci(n-2);

为此先按照语句分析如下:(PS:经网上相关资料提示:递归算法的本质是先递归后回溯,从而求得最终结果。以下只是本人根据程序运行结果做出的推测分析,如有错误,欢迎各位圆友指正~)

(1)Fibonacci(4) = Fibonacci(3) + Fibonacci(2),此时会首先输出数字4;

(2)接着执行Fibonacci(3) = Fibonacci(2) + Fibonacci(1),此时会首先输出数字3;

(3)接着执行(2)中Fibonacci(2),递归结束,此时会首先输出数字2;

(4)接着执行(2)中Fibonacci(1),递归结束,此时会首先输出数字1;

(5)接着执行(1)中Fibonacci(2),递归结束,此时会首先输出数字2;

(6)上面(1)~(5)步中仅仅只完成了递归算法,并未完成求取Fibonacci(4)的具体值步骤,此时,正式开始回溯求取Fibonacci(4),即Fibonacci(4) = Fibonacci(3) + Fibonacci(2),此时输出数字4;

(7)回溯求取(6)中Fibonacci(3)= Fibonacci(2) + Fibonacci(1),此时输出数字3;

(8)回溯求取(7)中Fibonacci(2)值,其在(3)中已获得为1,此时输出数字2;

(9)回溯求取(7)中Fibonacci(1)值,其在(4)中已获得为1,此时输出数字1,此时求得(6)中Fibonacci(3) = 2;

(10)回溯求取(6)中Fibonacci(2)值,其在(5)中已获得为1,此时输出数字2,此时求得6)中Fibonacci(2) = 1;

(11)输出最终结果Fibonacci(4) = 2+1 =3。

上述执行步骤求取Fibonacci(4)简单示意图:
递归执行顺序的探究

2.2 定位输出测试
由2.1中对于斐波那契数问题的执行顺序探讨让我明白了一条递归的实质——先递归后回溯。在本文的问题中,还要谨记一点——递归的执行顺序遵循栈的特性——先进后出。

先看本文所述问题具体测试代码:

package com.liuzhen.chapterThree;

public class TravelingSalesman {
    
    public int count = 0;
    /*
     * start为开始进行排序的位置
     * step为当前正在排序的位置
     * n为需要排序的总位置数
     * Max为n!值
     */
    public  void Arrange(int[] A,int start,int step,int n,int Max){
        if(step == 2)
            System.out.println("第"+(++count)+"次走完一圈");
        if(count == Max)
            System.out.println("已完成!!!");
        else{
            System.out.println("准备进入for循环");
            for(int i = start;i < n;i++){
                swapArray(A,start,i);
                System.out.println("递归调用前:"+" start值为"+start+",i的值为"+i);
                Arrange(A,start+1,step+1,n,Max);
                System.out.println("递归调用后:"+" start值为"+start+",i的值为"+i);
                swapArray(A,i,start);
            }
        }
    }
    
    public  void swapArray(int[] A,int p,int q){
        int temp = A[p];
        A[p] = A[q];
        A[q] = temp;
    }
    
    public static void main(String[] args){
        int[] A = {0,1};
        TravelingSalesman test = new TravelingSalesman();
        test.Arrange(A,0,0,2,2);
    }
}

运行结果:

准备进入for循环
递归调用前: start值为0,i的值为0
准备进入for循环
递归调用前: start值为1,i的值为1
第1次走完一圈
准备进入for循环
递归调用后: start值为1,i的值为1
递归调用后: start值为0,i的值为0
递归调用前: start值为0,i的值为1
准备进入for循环
递归调用前: start值为1,i的值为1
第2次走完一圈
已完成!!!
递归调用后: start值为1,i的值为1
递归调用后: start值为0,i的值为1

此处是求取数字0和1的不同排序,即有2!= 2种不同排序,此处依照代码及运行结果来分析其具体执行顺序:

(1)

准备进入for循环:

递归调用前: start值为0,i的值为0(程序初始化值start为0,i等于start值为0)

(2)

准备进入for循环:

递归调用前: start值为1,i的值为1(执行完一次递归后,start值变为1,i等于start值也为1)

(3)

第1次走完一圈(输出此句,表示已经执行完两次递归,start值变为了2)

准备进入for循环:(此时,start值为2,即准备开始回溯,执行未完成的for循环)

递归调用后: start值为1,i的值为1(此处,对照栈的特性,开始进行(2)中未完成的for循环,输出此句后,将结束(2)中的for循环)

递归调用后: start值为0,i的值为0(此处,对照栈的特性,开始进行(1)中未完成的for循环,i值将要加1)

递归调用前: start值为0,i的值为1(此处,进行了(1)中一次for循环后,就要开始执行一次递归语句,start值将要加1)

(4)

准备进入for循环:

递归调用前: start值为1,i的值为1(此处,是执行(3)中递归语句的执行输出结果,此时也要开始执行一次递归语句,start值将要加1)

(5)

第2次走完一圈(此时,start值有变成了2)

已完成!!!

递归调用后: start值为1,i的值为1(此处,执行步骤(4)中未完成for循环的回溯,进行for循环)

递归调用后: start值为0,i的值为1(此处,执行步骤(3)中未完成for循环的回溯,进行for循环)

上述是对2!次不同排序的递归执行顺序分析,下面我们可以来看看对于3!次不同排序的递归执行顺序结果,看看其执行顺序是否满足栈——先进后出的特性,

PS:此处对上述代码中定义数字进行稍微修改,修改如下:

if(step == 3)
            System.out.println("第"+(++count)+"次走完一圈");


public static void main(String[] args){
        int[] A = {0,1,2};
        TravelingSalesman test = new TravelingSalesman();
        test.Arrange(A,0,0,3,6);
    }

运行结果

准备进入for循环
递归调用前: start值为0,i的值为0
准备进入for循环
递归调用前: start值为1,i的值为1
准备进入for循环
递归调用前: start值为2,i的值为2
第1次走完一圈
准备进入for循环
递归调用后: start值为2,i的值为2
递归调用后: start值为1,i的值为1
递归调用前: start值为1,i的值为2(此处即将执行一次递归)
准备进入for循环
递归调用前: start值为2,i的值为2
第2次走完一圈
准备进入for循环
递归调用后: start值为2,i的值为2
递归调用后: start值为1,i的值为2
递归调用后: start值为0,i的值为0
递归调用前: start值为0,i的值为1
准备进入for循环
递归调用前: start值为1,i的值为1
准备进入for循环
递归调用前: start值为2,i的值为2
第3次走完一圈
准备进入for循环
递归调用后: start值为2,i的值为2
递归调用后: start值为1,i的值为1
递归调用前: start值为1,i的值为2
准备进入for循环
递归调用前: start值为2,i的值为2
第4次走完一圈
准备进入for循环
递归调用后: start值为2,i的值为2
递归调用后: start值为1,i的值为2
递归调用后: start值为0,i的值为1
递归调用前: start值为0,i的值为2
准备进入for循环
递归调用前: start值为1,i的值为1
准备进入for循环
递归调用前: start值为2,i的值为2
第5次走完一圈
准备进入for循环
递归调用后: start值为2,i的值为2
递归调用后: start值为1,i的值为1
递归调用前: start值为1,i的值为2
准备进入for循环
递归调用前: start值为2,i的值为2
第6次走完一圈
已完成!!!
递归调用后: start值为2,i的值为2
递归调用后: start值为1,i的值为2
递归调用后: start值为0,i的值为2

可以看出,运行结果明显满足上述中2!次运行结果的分析及推测结论。

2.3 回顾总结
通过以上的分析及上机输出测试,可以初步得出递归算法执行顺序满足如下两点:

(1)先执行递归,后进行回溯; (2)执行顺序满足栈的特性——先进后出。
上一篇:python – 如何从range()函数中获取最后一个数字?


下一篇:如何优雅的计算Fibonacci数列