Попробуйте
(defn pow [x n]
(loop [x x n n r 1]
(cond
(= n 0) r
(even? n) (recur (* x x) (/ n 2) r)
:else (recur x (dec n) (* r x)))))
для хвостового рекурсивного решения O (log n), если вы хотите реализовать его самостоятельно (поддерживает только натуральные числа). Очевидно, что лучшим решением будет использование библиотечных функций, на которые указывали другие.