甚至？方案中的函数（Racket 博士）

Question

我正在尝试在Scheme中编写一个程序来使用快速幂算法/递归来计算幂函数的结果。该算法应该是正确的，但我的语法在某些地方是错误的。程序可以编译，但当我输入一个基数和指数进行测试时，Dr. Racket 冻结并耗尽内存。很难找到有关（偶数？）函数应如何出现在方案代码中的在线示例。我认为这可能会破坏我的语法。计划新手，因此任何帮助将不胜感激。

(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?与if- 你用它来测试一个数字是否为偶数不同。
它没有“分支”：

> (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"

您可以将其用作条件测试：

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

如果您想测试多个条件，可以方便地使用cond而不是if：

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

但这并不是 DrRacket“冻结”的原因。

原因是除法不是整数除法，而是实际上产生精确的小数结果：

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

所以你永远不会到达终止情况。

您应该使用以下quotient程序：

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

利用该sqr过程并将括号从“C 样式”更改为“方案样式”，它可能如下所示：

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

或者

(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

旁注：当您寻找问题时，交互窗口对于测试一小部分代码非常有用。