The function written in this pic is for explaining recursion. It says that the function takes T(n) time to run but it contains a recursive call and then it takes T(n-1) time to run. But we know that function takes T(n) time and same function call is taken then it should again take T(n) time because function is doing same thing as before. Please tell me if i am wrong in understanding the concept or the concept is wrongly explained in the code.

CodePudding user response：

The image is this

void Test(int n) {
    if (n > 0) {
        printf("%d",n);        // 1
        Test(n-1);             // T(n-1)
    }
}
// T(n) = T(n-1)   1

By definition T(n) is the time taken by Test(n). Also T(n-1) is just a label for "time taken to call Test(n-1)".

As the function only calls printf which is constant complexity, it is counted as 1 instruction, and calls Test(n-1), its total runtime is T(n) = T(n-1) 1.

But we know that function takes T(n) time and same function call is taken then it should again take T(n) time because function is doing same thing as before.

No, T(n-1) is not the same as T(n) because Test(n) is not doing the same as Test(n-1). Test(n) is doing the same as Test(n-1) plus calling printf once.