相关疑难解决方法(0)

f (int n){
    if (n<=0){
        return 1;
    }
    return f(n-1) + f(n-1);
}

假设我们做了f(4).我的想法是它会是O(2 ^ n),从那以后为了找到f(n-1)+ f(n-1),我们必须将f(n-1)= f(3)推到调用堆栈两次,然后f(2)调用堆栈的四倍等.但是,我得到的这本书说是O(n).为什么这是真的？