Question

矩阵连乘的递归问题

void Traceback(int i, int j, int **s)
{ if (i == j) return;
Traceback(i, s[i][j], s);
Traceback(s[i][j] + 1, j,s);
cout << "Multiply A " << i << ", " << s[i][j];
cout <<" and A " << (s[i][j] + 1) << " , " << j << endl }
这段代码是通过s[i][j]，确定加括号方式，构造矩阵连乘的最优解 但是这个递归看不懂 为什么会每递归一次都有输出呢 还有i=j的时候 返回到哪里去了 ？

能以图片的例子给我说一下Traceback(1,n,s)的详细步骤麽？谢谢~（n是矩阵个数，**s是记录最优的断点位置。）

Answer 1

由于输出是在Traceback内部，因此每次递归调用Traceback，只要不是i==j而return，都会执行到cout部分。

i==j时，返回到递归调用的上一级了。

追问

可是每次Traceback(i, s[i][j], s);的时候不都是从头调用么 直到I=J的时候再执行Traceback(s[i][j] + 1, j,s);为什么会跳过第二个 Traceback(s[i][j] + 1, j,s); 就COUT了呢？

追答

递归return返回到上一级的时候，如果上一级本身就是第二个Traceback，那就直接进入cout了。建议使用VC或VS的递归栈查看功能来获取每一层递归Traceback是在哪一行。

追问

那第一个TRACEBACK还是不能RETURN啊

追答

第一个Traceback要全部走完才会return，可能会递归得很深。最终会return的。