最长公共子串递归函数执行逻辑追踪相关疑问

你提供的实现代码如下：

int recursive_substr(string a, string b, int m, int n,int count){
    if (m == -1 || n == -1) return count;
    if (a[m] == b[n]) {
        count = recursive_substr(a,b,m-1,n-1,++count);
    }
    return max(count,max(recursive_substr(a,b,m,n-1,0),recursive_substr(a,b,m-1,n,0)));
}

问题1：当前字符匹配时count的计算逻辑 #

• 当a[m]与b[n]相等时，说明当前两个字符可以归入正在统计的连续公共子串，代码先执行++count把当前匹配的长度加1，再作为参数传入递归调用，向前对比两个字符串的前一位字符。
• 递归调用会沿着两个字符串同时前移的路径继续统计连续匹配的长度，直到遇到不匹配的字符或者走到字符串头部，最终返回的连续匹配长度会赋值给当前层的count变量。比如当前位置往前还有2个连续匹配的字符，那递归返回后count值就会是3，对应3位连续公共子串。

问题2：最后一行count的取值来源 #

• 最后一行用到的count是当前函数层经过前序逻辑处理后的最终值：如果当前字符匹配，就是递归调用更新后的值；如果当前字符不匹配，就是本次函数调用传入的初始count值。
• 最后一行的逻辑是把三个可能的结果取最大值：当前已统计到的连续公共子串长度、跳过b当前字符重新统计的最长长度、跳过a当前字符重新统计的最长长度，三者的最大值就是当前状态下的最长公共子串长度。

递归原理学习建议 #

• 先从基础递归场景入手练习：比如阶乘计算、斐波那契数列求值、汉诺塔问题，手动模拟小输入下的递归调用栈，理清每一层的入参、返回值和变量变化。
• 处理字符串、数组类递归问题时，可以用画图的方式标记每一层递归对应的下标范围和中间结果，避免混淆多层调用的同名变量。
• 可以尝试把递归逻辑改写成迭代+手动模拟栈的实现，和原递归实现做执行流程对比，能更直观理解递归的底层运行逻辑。

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