Tail-Recursive Power Function in Scheme

Question

I am having trouble writing a tail-recursive power function in scheme. I want to write the function using a helper function. I know that I need to have a parameter to hold an accumulated value, but I am stuck after that. My code is as follows.

(define (pow-tr a b)
(define (pow-tr-h result)
  (if (= b 0)
     result
     pow-tr a (- b 1))(* result a)) pow-tr-h 1)

I edited my code, and now it works. It is as follows:

(define (pow-tr2 a b)
 (define (pow-tr2-h a b result)
  (if (= 0 b)
    result
    (pow-tr2-h a (- b 1) (* result a))))
 (pow-tr2-h a b 1))

Can someone explain to me why the helper function should have the same parameters as the main function. I am having a hard time trying to think of why this is necessary.

Answer 1

It's not correct to state that "the helper function should have the same parameters as the main function". You only need to pass the parameters that are going to change in each iteration - in the example, the exponent and the accumulated result. For instance, this will work fine without passing the base as a parameter:

(define (pow-tr2 a b)
  (define (pow-tr2-h b result)
    (if (= b 0)
        result
        (pow-tr2-h (- b 1) (* result a))))
  (pow-tr2-h b 1))

It works because the inner, helper procedure can "see" the a parameter defined in the outer, main procedure. And because the base is never going to change, we don't have to pass it around. To read more about this, take a look at the section titled "Internal definitions and block structure" in the wonderful SICP book.

Now that you're using helper procedures, it'd be a good idea to start using named let, a very handy syntax for writing helpers without explicitly coding an inner procedure. The above code is equivalent to this:

(define (pow-tr2 a b)
  (let pow-tr2-h [(b b) (result 1)]
    (if (= b 0)
        result
        (pow-tr2-h (- b 1) (* result a)))))

Answer 2

Even though it has the same name, it's not the same parameter. If you dug into what the interpreter is doing you'll see "a" defined twice. Once for the local scope, but it still remembers the "a" on the outer scope. When the interpreter invokes a function it tries to bind the values of the arguments to the formal parameters.

The reason that you pass the values through rather mutating state like you would likely do in an algol family language is that by not mutating state you can use a substitution model to reason about the behaviour of procedures. That same procedure called at anytime with arguments will yeild the same result as it is called from anywhere else with the same arguments.

In a purely functional style values never change, rather you keep calling the function with new values. The compiler should be able to write code in a tight loop that updates the values in place on the stack (tail call elimination). This way you can worry more about the correctness of the algorithm rather than acting as a human compiler, which truth be told is a very inefficient machine-task pairing.

Answer 3

(define (power a b)
  (if (zero? b)
   1
  (* a (power a (- b 1)))))


(display (power 3.5 3))