Racket// recursive function

Question

as the title says im trying to code recursive for x^n without the expt function. If n is even it should: (x^n/2)^2 otherwise when its uneven x*x(^n-1) and obviously n=0 should be 1.

(define fast-power (lambda (x n) (cond [(and (number? x) (naturalnumber0? n)) (fast-power-internal x n)] [else (error 'fast-power "invalid input.")])))

(define (fast-power-internal x n) (cond n 0) 1] [ (even? n) ??? else ???

(define (naturalnumber0? n) (if (and (isinterger? n) (<= 0 n)) true false))

(define (isinterger? x ) x (floor x)) 0))

on the ??? lines im not sure how to make it recursive with 2 variables. Can anyone give me a hint?

Answer 1

There are several errors with your attempt. Starting with a simple function definition -

(define (isinterger? x ) x (floor x)) 0))

Let's add some line breaks and inline comments -

(define (isinterger? x )
  x          ; ignored
  (floor x)) ; end of function

0))          ; trailing syntax error

Note racket has many built-ins for identifying number types. integer? natural? zero? positive? even? etc. You can implement them yourself if you are careful to avoid mistakes but we will use Racket's in the section below.

The problem defines the result in expressions using ^. I would suggest to first rewrite these without ^

When n is zero -

1

(inductive: n is non-zero) When n is even -

(x^n/2)^2
(x^n/2) * (x^n/2)
f(x, n/2) * f(x, n/2) where f is fast-power

Translated to scheme -

(* (fast-power x (quotient n 2))
   (fast-power x (quotient n 2)))

We can avoid duplicate computation using let assignment -

(let ((r (fast-power x (quotient n 2))))
  (* r r)))

(inductive: n is non-zero, n is non-even) Otherwise n is odd -

x * x^(n-1) x * f(x n-1) where f is fast-power

Translated to scheme -

(* x (fast-power x (- n 1)))

As for your recursive function, I don't think you need an auxiliary helper. I find it useful to identify error cases before attempting the recursive logic. The cond expression is only concerned with the "happy path" of the program -

(define (invariant condition message)
  (if condition
      (void)
      (error 'invariant message)))

(define (fast-power x n)
  (invariant (number? x) "x must be a number")
  (invariant (natural? n) "n must be a natural number")
  (cond ((zero? n) 1)
        ((even? n)
         (let ((r (fast-power x (quotient n 2))))
           (* r r)))
        (else (* x (fast-power x (- n 1))))))

(fast-power 2 32) ; 4294967296
(fast-power 1.5 4) ; 5.0625
(fast-power 1.5 4.5) ; ⚠️ invariant: n must be a natural number

Note: quotient returns the integer result of division. / returns a number.

Note: Use the Racket > Reindent option to format the source code for you automatically.

---

contracts

Using invariant like I did above is an effective means for handling bad inputs to your programs, however writing code like this can feel like a chore. Racket makes all of this easier with contracts. Let's see fast-power written using a contract -

(require racket/contract)

(define/contract (fast-power x n)
  (-> number? natural? number?) ; contract
  (cond ((zero? n) 1)
        ((even? n)
         (let ((r (fast-power x (quotient n 2))))
           (* r r)))
        (else (* x (fast-power x (- n 1))))))

The contract is explained as -

(-> 
  number?   ; contract of argument 1
  natural?  ; contract of argument 2
            ; ...
  number?)  ; contract of return value

Re-run the program to see the contract enforced -

(fast-power 2 32) ; 4294967296
(fast-power 1.5 4) ; 5.0625
(fast-power 1.5 4.5) ; ⚠️ fast-power: contract violation

Our contract enforces n must be a natural number

fast-power: contract violation
  expected: natural?
  given: 4.5
  in: the 2nd argument of
      (-> number? natural? number?)
  contract from: (function fast-power)
  ...

Note: define/contract is a macro provided by the racket/contract.