c - 递归函数的增长顺序

Question

以下问题是在 2001 年 GRE 计算机科学考试中提出的。

Q-67:考虑以下C 代码。

int f(int x) {
    if(x<1) {
        return 1;
    } else {
        return f(x-1)+g(x);
    }
}

int g(int x) {
    if(x<2) {
        return 1;
    } else {
        return f(x-1)+g(x/2);
    }   
}

以下哪项最能描述 f(x) 作为 x 函数的增长？

(A) 对数 (B) 线性 (C) 二次 (D) 立方 (E) 指数

顺便说一句，正确答案是(E)指数(在其答案中提到)。但是，我不知道解决这个问题的确切方法。

有人能解决上述递归关系吗？您有任何替代方法吗？

请分享您的观点。

Answer 1

我认为这可以简化为 f(x) >= f(x-1)+f(x-1) 对于 x>1， 因为g(x) = f(x-1)+g(x/2) >= f(x-1) 对于 x>1。 第一个不等式就是 f(x) >= 2*f(x-1)，从这里很容易推导出 f(x) >= 2^x*f( 1)(每当x增加1时，f的值至少翻倍)。