Java递归未终止原因分析及递归、嵌套递归学习方法咨询

问题背景 #

刚接触Java递归，对运行机制有困惑，现有如下递归代码：

package roughworkp;

public class r_class {

    public static void main(String[] args) {
        System.out.println(check(5));
    }

    public static int check(int root) {
        int c = 0;
        if (root == 0) {
            return 0;
        }
        System.out.print("first");
        int l = check(root - 1);
        System.out.print("in l" + l + " ");

        int r = check(root - 1);
        System.out.println("in r" + r + " ");
//      System.out.print("i am in here"+" "+(++c)+" ");
//      ++c;
//      System.out.println();
        return Math.max(l, r)+1;
    }
}

运行输出：

firstfirstfirstfirstfirstin l0 in r0
in l1 firstin l0 in r0
in r1
in l2 firstfirstin l0 in r0
in l1 firstin l0 in r0
in r1
in r2
in l3 firstfirstfirstin l0 in r0
in l1 firstin l0 in r0
in r1
in l2 firstfirstin l0 in r0
in l1 firstin l0 in r0
in r1
in r2
in r3
in l4 firstfirstfirstfirstin l0 in r0
in l1 firstin l0 in r0
in r1
in l2 firstfirstin l0 in r0
in l1 firstin l0 in r0
in r1
in r2
in l3 firstfirstfirstin l0 in r0
in l1 firstin l0 in r0
in r1
in l2 firstfirstin l0 in r0
in l1 firstin l0 in r0
in r1
in r2
in r3
in r4
5

疑问与解答 #

1. 递归为何未在预期位置终止？ #

递归其实是正常终止的，你觉得没在预期位置终止，是没搞懂递归的调用栈流程：

• 当root=0时，直接返回0，这是明确的终止条件，每次到这里都会停止当前分支的递归。
• 但每个非终止的check方法，在获取l的递归返回后，还会再调用一次check(root-1)获取r，这导致每个节点都会触发两次递归调用，整个调用树是指数级展开的（比如check(5)触发2个check(4)，每个check(4)又触发2个check(3)，以此类推），所以输出内容会比你预期的多很多，不是没终止，是分支调用的次数超出了预期。

2. 注释的变量c为何未递增？ #

首先这部分代码被注释掉了，自然不会执行递增操作；就算取消注释，c是方法局部变量，每次进入check方法都会重新初始化c=0，每个递归调用的c都是独立的，不会共享状态。比如check(5)里的c和check(4)里的c是两个完全不同的变量，各自递增不会影响对方，所以你看不到全局递增的效果。

3. 每次递归计算最大值的逻辑是否合理？ #

逻辑本身是自洽的，但这里l和r都是check(root-1)的返回值，两者结果完全一致，所以Math.max(l,r)其实等于l（或r），最终返回的就是root的值（比如check(5)返回5，check(4)返回4）。如果你的目的是模拟计算二叉树的最大深度，这个逻辑框架没问题，但因为当前左右分支是完全相同的递归调用，所以属于冗余计算，结果等价于直接返回root。

递归、嵌套递归入门与深入学习方法 #

入门阶段 #

• 从基础案例入手：先写阶乘、斐波那契数列这类简单递归，手动画调用栈（标注每个方法调用的参数、返回值、执行顺序），搞懂递归的“去”（逐层调用过程）和“归”（逐层返回过程）。
• 先确定终止条件：写递归代码的第一步必须明确终止条件，没有终止条件会直接触发栈溢出，终止条件要能让递归链最终停下来。
• 拆分问题找递推关系：把大问题拆成和原问题结构一致的小问题，比如阶乘n! = n*(n-1)!，核心是找到这种可复用的递推逻辑。

深入阶段 #

• 分析复杂度：学会分析递归的时间、空间复杂度，比如你这段代码的时间复杂度是O(2^n)，空间复杂度是O(n)（递归栈深度），可以用主定理来推导常见递归结构的复杂度。
• 嵌套递归（分治类）：学习归并排序、快速排序这类分治算法，或者汉诺塔问题，理解如何把问题拆成多个子问题，再合并子问题的结果得到最终答案。
• 尾递归理解：了解什么是尾递归（递归调用是方法的最后一步操作），虽然Java不支持尾递归优化，但理解其原理能帮你更清晰地对比普通递归的差异。
• 递归转迭代：把递归代码改成迭代实现（比如用栈模拟递归调用栈），这个过程能让你彻底搞懂递归的运行机制。

内容的提问来源于stack exchange，提问作者sleep