This is the explanation on recursion tracing, and I can't understand some logic in it. What is the logic?

Question

Consider:

The function written in this picture 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 the same function call is taken. Then it should again take T(n) time, because the function is doing the same thing as before. Am I wrong in understanding the concept or is the concept wrongly explained in the code?

Answer 1

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.