Which one is the correct way to change functional notation while solving recurrence relation?
"Why we can change any recurrence relation like this?"


Answer: by the definition of function. This is about pure algebra. 

Let me explain slowly and clearly. (To someone who just learned the definition of function, I should probably explain much slower with more explanation regarding the definition of domain, range, correspondence, change of dumb variables etc. To someone with a master degree in math, there is really nothing needed to explain. The speed of explanation below is somewhat arbitrarily in-between, since I do not know your level. If you think some stuff is too obvious to you, just skip it. Otherwise, comment below to tell me which part is still puzzling to you.)

Suppose we have a function, $T:\Bbb N\to\Bbb N$ defined by $T(2^{n}) = 2T(2^{n/2}) + n$. Let us define a new function, $S: \Bbb N\to\Bbb N$ by $s(m) = T(2^m)$, that is, $s(1) = T(2)$, $s(2) = T(4)$, $s(3) = T(8)$, etc. Since $m$ is an independent variable, we can also substitute $m/2$ for $m$ to obtain $s(m/2)=T(2^{m/2})$. So we will have,
$$s(m) = T(2^m) = 2T(2^{m/2}) + m = 2s(m/2) + m $$


  how will the following relation $T(2^{n}) = T(2^{n-1}) + 1$ be changed? Which change is correct?  $S(n) = S(n/2) + 1$ or $S(n) = S(n-1) + 1$?


If we define function $S: \Bbb Z\to\Bbb Z$ by $S(m) = T(m)$, i.e., $S$ is the same function as $T$, then we have, for any $n\in\Bbb Z$ that is a power of 2, i.e., $n=2^m$ for some $m$,
$$S(n) = S(2^m) = T(2^m) = T(2^{m-1}) + 1 = S(2^{m-1}) + 1 = S(2^m/2)+1 =S(n/2)+1. $$

On the other hand, if we define function $S: \Bbb Z\to\Bbb Z$ by $S(m) = T(2^m)$, then substituting $m-1$ for $m$, we have $S(m-1)=T(2^{m-1})$. So,
$$S(m) = T(2^m) = T(2^{m-1}) + 1 = S(m-1) + 1$$

In summary, either one of $S(n) = S(n/2) + 1$ and $S(n) = S(n-1) + 1$ can be correct. Which one is correct depends on how you define $S$. Once you have write down the definition of $S$, it will be clear which one is correct and which one is wrong. In other words, you have to specify what is $S$ first.