recursion - 甚至？ Scheme 中的函数(Dr. Racket)

Question

我正在尝试在 Scheme 中编写一个程序，以使用快速幂算法/递归计算幂函数的结果。该算法应该是正确的，但是我的语法在某处不正确。程序可以编译，但是当我输入一个 base 和 exp 进行测试时，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 风格”更改为“Scheme 风格”，它可能如下所示:

(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

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