时间戳

首页 > 解决方案 > 在这种情况下，递归究竟是如何工作的？

java - 在这种情况下，递归究竟是如何工作的？

问题描述

我是这个论坛的新手，我希望我不会犯任何错误。这是我的问题。我想我了解递归的基本原理及其实现，但是我很难理解计算机在执行递归代码时正在执行的确切步骤。

这是一个例子：

公共类主要{

public static void MyAlgorithm (int [] A, int l, int r ) {
    if (l<r) {
        int m = (l+r)/2;
        MyAlgorithm(A, l, m);

        for (int i = l; i<=r; i++) {
            System.out.println(A[i]);
        }

        MyAlgorithm(A, m+1, r);
    }


}
public static void main (String args[]) {

    int [] A = {1,2,3,4};

    MyAlgorithm (A, 0, 3);
}

}

输出为：12123434

但这究竟是如何工作的？首先，代码将 m 计算为 2。然后在子数组 (1,2) 上再次执行该方法并将其放入堆栈。然后它再次这样做，取一半并将 1 放入堆栈。据我了解这个问题，它然后停止，从堆栈中弹出 1 并打印它。但是它什么时候将 2 单独放入堆栈？它究竟什么时候从另一半开始递归部分？我根本无法真正理解计算机如何执行单个步骤以及它如何“知道”何时开始递归调用数组的另一半。我希望你能理解我的问题，我很感激每一个回答！

提前致谢 ：）

标签： javarecursionstack

解决方案

执行调用将是这样的

MyAlgorithm(A,0,3) 
    (l < r : true)
     m = (0+3)/2=1
     MyAlgorithm(A,0,1) 
            (l < r : true) 
            m = (0+1)/2=0
            MyAlgorithm(A,0,0) 
                (l < r : false) return

            loop from l=0 to r=1
            System.out.println(A[0]);
            System.out.println(A[1]);

            //MyAlgorithm(A,m+1,r)
            MyAlgorithm(A,1,1) 
                (l < r : false) return

    loop from 1=0 to r=3
    System.out.println(A[0]);
    System.out.println(A[1]);
    System.out.println(A[3]);
    System.out.println(A[4]);

    //MyAlgorithm(A,m+1,r)
    MyAlgorithm(A,2,3)
        (l < r : true)
        m=(2+3)/2 = 2
        MyAlgorithm(A,2,2)
            (l < r : false) return

    loop from 1=2 to r=3
    System.out.println(A[2]);
    System.out.println(A[3]);

    MyAlgorithm(A,3,3)
            (l < r : false) return      
return

这导致答案：12123434

推荐阅读