求助：仅允许递归调用，如何实现返回指定字符包裹的子串？

问题描述 #

只能递归调用theSub方法，不能使用其他方法或添加参数，需要实现返回被字符first和last包裹的子串。当前代码除基准情况外逻辑错误，还陷入无限递归。

原代码：

public static String theSub(String str, char first, char last) {
    if (str.length() == 0 ) {
        return str;
    }
    else if (str.charAt(0)==first) {
        return str.substring(1, str.length() - 1);
    }
  //infinite recursion..
    return theSub(str,first,last);
}

原代码问题分析 #

1. 无限递归原因：最后一行递归调用时传入的str和原参数完全一致，没有缩小问题规模，永远无法触发基准情况，导致死循环。
2. 逻辑不完整：仅判断首字符是否为first，未检查尾字符是否为last；同时没有处理首字符不是first的情况，直接进入无效递归。

修正后的代码 #

public static String theSub(String str, char first, char last) {
    // 基准情况：字符串长度不足2，无法被两个字符包裹，返回空串
    if (str.length() < 2) {
        return "";
    }
    // 首字符不是目标，递归处理去掉首字符后的子串
    if (str.charAt(0) != first) {
        return theSub(str.substring(1), first, last);
    }
    // 尾字符不是目标，递归处理去掉尾字符后的子串
    if (str.charAt(str.length() - 1) != last) {
        return theSub(str.substring(0, str.length() - 1), first, last);
    }
    // 首尾都匹配，返回中间包裹的子串
    return str.substring(1, str.length() - 1);
}

代码说明 #

• 基准情况调整：当字符串长度小于2时，不可能存在first和last包裹的子串，直接返回空串。
• 缩小问题规模：每次递归都会对str进行裁剪（去掉首字符或尾字符），确保递归深度有限，最终能触发基准情况。
• 完整逻辑判断：先检查首字符是否匹配，不匹配则裁剪首字符递归；再检查尾字符是否匹配，不匹配则裁剪尾字符递归；只有当首尾都匹配时，才返回中间的子串。

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