c - 递归函数的空间复杂度(时间和空间)

下面是递归函数，并且没有计算时间和空间复杂度。我看了一些资料，但对我的理解还不够清楚有谁能用最简单的方法解释一下解决问题的方法，并回答这个问题吗？
顺便说一下，我试图解决时间复杂度，我发现O（2 ^ n）。对吗？

int func(int n) {
     if (n < 3)
         return 3;
     else {
         return func(n-3)*func(n-3);
     }
}

最佳答案

是的，时间复杂度确实是O(2 ^ n)。
时间复杂度的递推关系为：
T(n) = 2 * T(n - 3)
应用上述公式k次：
T(n) = 2 * 2 * 2 ... k times * T(n - 3 * k) = 2 ^ k * T(n - 3k)
当k是n/3时，T(n) = 2 ^ k = 2 ^ (n / 3) = O(2 ^ n)
一次只有一个函数在运行，堆栈深度最大可以k。
因此，空间复杂度n / 3或O(n)

关于c - 递归函数的空间复杂度(时间和空间)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53361837/