#include <iostream>
using namespace std;
int g(int n) {
if (n == 1) return 1;
return 2 * g(n - 1) + 1;
}
int main() {
cout << g(5) << endl;
return 0;
}
- (1) 程序输出结果是______。（4 分）
- (2) 函数 g(n) 的闭式（通项公式）是______。（5 分）
- (3) 该函数的时间复杂度和空间复杂度分别约为多少？（5 分）
答案解析
（1）g(1)=1，g(2)=3，g(3)=7，g(4)=15，g(5)=31，输出 31。（2）g(n)=2ⁿ-1。（3）时间 O(n)（递推 n 次）；空间 O(n)（递归栈深度 n）。