甚至？ Scheme 中的函数（Dr. Racket）

Question

我正在尝试在 Scheme 中编写一个程序来计算使用快速幂 algorithm/recursion 的幂函数的结果。该算法应该是正确的，但是我的语法在某处不正确。程序可以编译，但是当我输入一个 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

if 最多只能带 2 个子句，then 和 else 没有关键字。在这种情况下，您可以使用嵌套 if 或 cond。以下是 cond 的示例：

(cond ((= expr 0) 1)
      ((even? exp) #| do even ... |#)
      (else #| do odd |#))

Answer 2

您似乎在使用 even?，好像它是某种行为类似于 if 的宏。但是 even? 是一个接受一个参数的常规函数，所以你应该写成 (even? exp) 而不是 (even? exp evaluate-if-even evaluate-if-not-even)。这意味着 even? 的 return 值需要它自己的 if 表达式：

(if base-case
   1
   (if (even? exp)
       evaluate-if-even
       evaluate-if-not-even))

...这意味着您应该改用 cond。

或者，您可以定义一个按照您认为的方式工作的宏 even?。我们称它为 if-even:

(define-syntax if-even
    (syntax-rules ()
       ((_ n evaluate-if-even evaluate-if-not-even)
        (if (even? n) evaluate-if-even evaluate-if-not-even))))

然后用if-even替换原来程序中的even?。不过，更正您对 even? 的使用然后切换到 cond 而不是 if 是更好的选择。

Answer 3

even? 与 if 不相似 - 你用它来测试 one 数字是否是偶数。
它没有 "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"

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

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

如果要测试几个条件，用cond代替if比较方便：

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

但这不是 DrRacket "freezing" 的原因。

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

> (/ 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 style" 更改为 "Scheme style"，它可能如下所示：

(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

旁注：交互 window 在您查找问题时对于测试小部分代码非常有用。

甚至？ Scheme 中的函数（Dr. Racket）

Even? function in Scheme (Dr. Racket)

recursion

scheme