I would add to the other answers the fact that the third branch of the function i.e the case of $n$ is $odd$ suggests that in that case the function will be computed on a larger instance ($n$ is lower than $3n+1$). So there is more work to be done on that computation branch.

Other recurrence relations that we encounter (for example in the case of merge sort $T(n) = 2T(n/2) +n$) adhere to the division of a problem into subproblems for instances with smaller size. Those reccurences degenerate naturally into base case(s), namely $T(0)$ or $T(1)$ which are known. So standard mathematical tools for analyzing the reccurence can be used, like the master theorem.

In the case of collatz function we are not able to infer directly from the reccurence that the case of $3n+1$ will eventually deteriorate using standard mathematical tools of reccurences. This is a topic to be resolved by looking at the problem itself, not the reccurence that describes it.

I would add to the other answers the fact that the third branch of the function i.e the case of $n$ is $odd$ suggests that in that case the function will be computed on a larger instance ($n$ is lower than $3n+1$). So there is more work to be done on that computation branch.

Other recurrence relations that we encounter (for example in the case of merge sort $T(n) = 2T(n/2) +n$) adhere to the division of a problem into subproblems for instances with smaller size. Those reccurences degenerate naturally into base case(s), namely $T(0)$ or $T(1)$ which are known. So, standard mathematical tools for analyzing the reccurence can be used, like the master theorem.

In the case of collatz function we are not able to infer directly from the reccurence that the case of $3n+1$ will eventually deteriorate using standard mathematical tools of reccurences. This is a topic to be resolved by looking at the problem itself, not the reccurence that describes it.