recurrence relation 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