递归内递归如何求解时间复杂度？

Question

void func1()
{
    ...
    func2();
    ...
}

func1是一个递归，func2也是一个递归，这两个递归没有相互关系，即不是互递归。那么如果我要求解func1的时间复杂度，是否可以先单独求出func2的时间复杂度，假如是t2，然后利用这个t2来求解func1呢？

如果不可以，请给下证明思路。（个人觉得不可以）

Answer 1

首先，不用说求算法复杂度了，就是确定这个函数能是否能返回（即不会进入死循环、无限递归）也是不可能的，参阅图灵停机问题。

其次，大多数能返回的递归函数，是能求出算法复杂度的，参阅原始递归函数。但个别情况下是无法求算法复杂度的，比如Ackermann函数。

Answer 2

确保两个递归都是会停机的情况下，理论上是可以根据fun2的时间+other（fun1中其它操作所用时间）来获得fun1的时间复杂度的