Write recurrence relation of below pseudocode that calculates x$^$n

power$2($x$,$n$)$:

if n$==0$:

return $1$

if n$==1$:

return x

if $($n$\%2)==0$:

return power$2($x$,$ n$//2)*$ power$2($x$,$n$//2)$

else:

return power$2($x$,$ n$//2)*$ power$2($x$,$n$//2)*$ x