Regarding the first part of your question: it's relatively simple to turn the procedure into tail-recursive form, we just have to pass an additional parameter to accumulate the answer. To avoid creating an additional procedure I'll use a named let
:
(define (exp x n)
(let loop ([x x] [n n] [acc 1])
(cond
((zero? n) acc)
((= n 1) (* x acc))
((even? n) (loop (* x x) (/ n 2) acc))
(else (loop (* x x) (/ (- n 1) 2) (* x acc))))))
And for the second question: the rule of thumb would be - if there's a way to halve the size of a problem at some point when making the recursive call (in such a way that the result can be computed accordingly), then that's a good sign that it might exist a logarithmic solution for it. Of course, that's not always so obvious.