C#递归算法逻辑理解困难 对应代码输出8,8求解析
算法逻辑与运行结果拆解
核心函数g(k)的规则定义
这是一段标准的斐波那契数列递归实现,运行逻辑分为两部分:
- 递归终止边界:当输入参数
k为1或2时,直接返回固定值1,不再向下拆分调用,避免递归无限循环 - 递归递推规则:当输入参数
k大于2时,返回值为g(k-1)与g(k-2)的计算结果之和,通过将大参数拆分为更小参数的方式重复调用自身,直到命中终止边界停止递归
逐节点推导计算结果
按照规则从最小的边界值开始向上推导,可得到每个参数对应的返回值:
g(1) = 1(命中终止边界)g(2) = 1(命中终止边界)g(3) = g(2) + g(1) = 1 + 1 = 2g(4) = g(3) + g(2) = 2 + 1 = 3g(5) = g(4) + g(3) = 3 + 2 = 5g(6) = g(5) + g(4) = 5 + 3 = 8
控制台输出的形成逻辑
Main函数中的输出语句为:
Console.WriteLine(g(4) + g(5) + "," + g(6));
按照C#的运算符执行顺序,先计算左侧整数加法段:g(4) + g(5) = 3 + 5 = 8,再将该结果与字符串,拼接,最后计算g(6)的值为8并拼接到字符串末尾,最终控制台输出的完整内容就是8,8,和实际运行结果完全匹配。
补充说明:这类递归实现存在大量重复计算的缺陷——比如计算
g(6)的过程中,会多次重复调用g(4)、g(3)等已经算过的节点,输入参数越大,冗余计算的耗时越高,实际开发中通常会通过缓存已计算结果、替换为迭代写法的方式做性能优化。
内容的提问来源于stack exchange,提问作者Hade Zedan
相关产品推荐
相关产品推荐

