Creating a tail-recursive power function in scheme

Question

I was wondering how do you implement a tail-resursive power function in scheme?

I've got my recursive one defined for scheme:

(define power-is-fun
  (lambda (x y)
    (cond [(= y 0)
           1]
          [(> y 0)
           (* (power-is-fun x (- y 1)) x)])))

But I can't quite figure out how the other one is supposed to be.

Answer 1

The answer is similar, you just have to pass the accumulated result as a parameter:

(define power-is-fun
  (lambda (x y acc)
    (cond [(= y 0)
           acc]
          [(> y 0)
           (power-is-fun x (- y 1) (* x acc))])))

Call it like this, notice that the initial value for acc is 1 (you can build a helper function for this, so you don't have to remember to pass the 1 every time):

(power-is-fun 2 3 1)
> 8

Some general pointers to transform a recursive procedure to a tail-recursion:

• Add an extra parameter to the function to hold the result accumulated so far
• Pass the initial value for the accumulator the first time you call the procedure, typically this is the same value that you'd have returned at the base case in a "normal" (non-tail-recursive) recursion.
• Return the accumulator at the base case of the recursion
• At the recursive step, update the accumulated result with a new value and pass it to the recursive call
• And the most important: when the time comes to call the recursion, make sure to call it as the last expression with no "additional work" to be performed. For example, in your original code you performed a multiplication after calling power-is-fun, whereas in the tail-recursive version, the call to power-is-fun is the last thing that happens before exiting the procedure