Java递归反转字符串到达空串base case仍能输出结果的原因

相关代码 #

public static void main(String[] args) {
    String str = "abc";
    String b = reverseString(str);
    System.out.println(b);
}

public static String reverseString(String a){
    if (a.isEmpty()){
        return a;
    }
    return reverseString(a.substring(1)) + a.charAt(0);
}

核心逻辑解释 #

递归执行到base case、传入的字符串参数a为空时，程序仍能正常打印反转后字符串的核心原因是：base case只是递归向下递推的终止点，不是整个方法的最终返回节点，空串只是拼接流程的起始值。
递归的完整执行分为两个阶段：

• 递推阶段：从初始调用开始，每一层都把当前字符串的首字符暂存，传入截断首字符的子串调用下一层递归，直到传入空串触发base case
• 回溯阶段：从base case返回空串开始，每一层拿到下一层的返回结果后，拼接之前暂存的首字符，把拼接结果返回给上一层，直到回到最外层的初始调用

以入参"abc"为例，完整执行链路如下：

• 初始调用reverseString("abc")：字符串非空，暂存字符'a'，调用reverseString("bc")等待结果
• 调用reverseString("bc")：字符串非空，暂存字符'b'，调用reverseString("c")等待结果
• 调用reverseString("c")：字符串非空，暂存字符'c'，调用reverseString("")等待结果
• 调用reverseString("")：触发base case，直接返回空串""
• 回到reverseString("c")层：拿到空串拼接'c'得到"c"，返回上一层
• 回到reverseString("bc")层：拿到"c"拼接'b'得到"cb"，返回上一层
• 回到reverseString("abc")层：拿到"cb"拼接'a'得到"cba"，返回给main方法完成打印

所有递归层暂存的字符都会保存在Java虚拟机的方法调用栈中，不会因为深层递归执行就丢失，最终回溯完成的拼接结果就是完整的反转字符串。

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