Even? function in Scheme (Dr. Racket)

Question

I'm trying to write a program in Scheme to compute the result of the power function using the fast power algorithm/recursion. The algorithm should be correct, but somewhere my syntax is off. The program compiles, but when I input a base and exp to test, Dr. Racket freezes up and runs out of memory. Having a difficult time locating online examples for how the (even?) function should appear in scheme code. I think this might be throwing my syntax off. New to scheme so any help would be much appreciated.

(define (powFun base exp)
    (if ( = exp 0)                       //base case
     1                                     
       (even? exp                        //if exp is even
          (*
            (powFun base ( / exp 2))
            (powFun base ( / exp 2))
          )

       (*
          (powFun base (- exp 1) )      // else if exp is odd
           base 
       )
     )
  )

)

Answer 1

even? is not similar to if - you use it to test whether one number is even.
It does not have "branches":

> (even? 2)
#t
> (even? 2 "even" "odd")
. . ..\..\Program Files (x86)\Racket\share\pkgs\drracket\drracket\private\rep.rkt:1088:24: even?: arity mismatch;
 the expected number of arguments does not match the given number
  expected: 1
  given: 3
  arguments...:
   2
   "even"
   "odd"

You can use it as a test in a conditional:

> (if (even? 2) "even" "odd")
"even"

If you want to test several conditions, it's convenient to use cond instead of if:

> (define x 3)
> (cond ((= x 1) "one")
         ((even? x) "even")
         (else "odd"))
"odd"

But that's not the reason for DrRacket "freezing".

The reason for that is that the division is not an integer division but actually produces an exact fractional result:

> (/ 1 2)
1/2
> (/ (/ 1 2) 2)
1/4
> (/ (/ (/ 1 2) 2) 2)
1/8

so you will never reach the terminating case.

You should use the quotient procedure:

> (quotient 3 2)
1
> (quotient 2 2)
1
> (quotient 1 2)
0

Making use of the sqr procedure and changing your brackets from "C style" to "Scheme style", it might look like this:

(define (powFun base exp)
    (if (= exp 0) 
        1                                     
       (if (even? exp)
           (sqr (powFun base (quotient exp 2)))
           (* (powFun base (- exp 1)) base))))

Or

(define (powFun base exp)
    (cond ((= exp 0) 1)                                    
          ((even? exp) (sqr (powFun base (quotient exp 2))))
          (else (* (powFun base (- exp 1)) base))))

> (powFun 2 3)
8
> (powFun 2 0)
1
> (powFun 2 300)
2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397376

Side note: the interaction window is extremely useful for testing small parts of code when you're looking for a problem.