递归查找数组最大元素时res变量取值逻辑的疑问
递归求最大值逻辑解析
你给出的代码转义后完整内容如下:
using namespace std; int A[]={1,3,4}; int max(int A[], int n){ if(n==1) return A[0]; int res = max(A,n-1); if(res>A[n-1]) return res; else return A[n-1]; } int main(){ cout<<max(A,3); }
你困惑的核心是没有注意到每一层递归拿到下层的返回值后,都会完成一次当前层的大小比较,再把更大的值向上返回,不是只返回最底层的A[0]。这个递归函数的作用本质是返回数组前n个元素的最大值。
完整调用流程追踪(以你给出的代码为例)
- 第一步:
main函数调用max(A, 3),目标是求数组前3个元素[1,3,4]的最大值 - 第二步:进入
max(A,3),n=3不满足n==1的终止条件,需要先执行max(A,2)获取前2个元素的最大值,赋值给res - 第三步:进入
max(A,2),n=2不满足终止条件,需要先执行max(A,1)获取前1个元素的最大值,赋值给res - 第四步:进入
max(A,1),n=1满足终止条件,直接返回A[0]的值1,回到max(A,2)层 - 第五步:
max(A,2)层的res现在被赋值为1,接下来比较res和A[1](值为3),3更大,所以max(A,2)返回3,回到max(A,3)层 - 第六步:
max(A,3)层的res现在被赋值为3,接下来比较res和A[2](值为4),4更大,所以max(A,3)返回4,最终输出结果为4
每一层的res拿到的都是前n-1个元素的最大值,不是固定的A[0],因为每一层递归都会完成一次比较后再向上返回结果。
内容的提问来源于stack exchange,提问作者atlant zogiani
相关产品推荐
相关产品推荐

