C语言递归程序执行逻辑分析及输出结果计算疑问

1. if语句执行逻辑 #

首先明确tot是递归函数，传入的参数j是数组的下标（从1开始计数），三个分支的逻辑如下：

• 第一个分支if (2*j <= MaxJ)：如果当前节点j存在左孩子（完全二叉树左孩子下标为2j，只要左孩子下标不超过最大索引8，说明左右孩子都有效/存在），那么当前节点的返回值等于左子树的总和 + 右子树的总和，也就是递归调用tot(2j)和tot(2j+1)的结果相加
• 第二个分支else if (j<=MaxJ)：如果当前节点没有孩子，但下标在合法范围内，说明是叶子节点，直接返回数组对应位置的值A[j]
• 第三个分支else：下标超出合法范围，返回0

你之前的推导错误在于忽略了第一个分支需要同时计算左右两个子树的返回值，不是仅递归左分支。

2. 结果60的计算过程 #

先明确数组各下标对应的值（注意C语言数组下标从0开始，这里函数用的j从1开始）：
A[1]=2, A[2]=3, A[3]=5, A[4]=7, A[5]=11, A[6]=13, A[7]=17, A[8]=19

递归展开计算过程：

• tot(1)：2*1=2 ≤8，返回tot(2) + tot(3)
  • 计算tot(2)：2*2=4 ≤8，返回tot(4) + tot(5)
    • 计算tot(4)：2*4=8 ≤8，返回tot(8) + tot(9)
      • tot(8)：2*8=16>8且8≤8，返回A[8]=19
      • tot(9)：9>8，返回0
      • 得tot(4)=19+0=19
    • 计算tot(5)：2*5=10>8且5≤8，返回A[5]=11
    • 得tot(2)=19+11=30
  • 计算tot(3)：2*3=6 ≤8，返回tot(6) + tot(7)
    • 计算tot(6)：2*6=12>8且6≤8，返回A[6]=13
    • 计算tot(7)：2*7=14>8且7≤8，返回A[7]=17
    • 得tot(3)=13+17=30
• 最终tot(1)=30+30=60

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