Racket//递归函数

Question

正如标题所说，我尝试在没有 expt 函数的情况下为 x^n 编写递归代码。如果 n 是偶数，则应该： (x^n/2)^2 否则当其不均匀 x*x(^n-1) 且显然 n=0 时应该是 1。

（定义快速功率 （拉姆达 (x n) （条件 [(and (number? x) (naturalnumber0? n)) (fast-power-internal x n)] [否则（错误“快速电源”无效输入。”）]）））

（定义（快速功率内部 x n） （条件 n 0) 1] [（偶数？n）？？？ 不然？？？

(定义(自然数0?n) (if (and (isinterger? n) (<= 0 n)) true false))

(定义 (是整数? x ) x（楼层 x））0））

在？？？我不知道如何使用 2 个变量使其递归。有人可以给我提示吗？

Answer 1

您的尝试存在多个错误。从简单的函数定义开始 -

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

让我们添加一些换行符和内联注释 -

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

0))          ; trailing syntax error

我认为你想写的是-

(define (integer? x)
  (eq? x (floor x))) 

Note 球拍有许多内置功能，用于识别号码类型。

integer?

natural?

zero?

positive?

even?

等。如果你小心避免错误，你可以自己实现它们，但我们将在下面的部分中使用 Racket。

问题使用

^

定义表达式中的结果。我建议首先重写这些而不使用

^

当

n

为零时 -

1

（归纳式：

n

非零）当

n

为偶数时 -

(x^n/2)^2
(x^n/2) * (x^n/2)
f(x, n/2) * f(x, n/2) 其中 f 是

fast-power

翻译为方案-

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

我们可以使用

let

赋值来避免重复计算 -

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

（归纳：

n

为非零，

n

为非偶数）否则

n

为奇数 -

x * x^(n-1) x * f(x n-1) 其中 f 是

fast-power

翻译为方案-

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

至于你的递归函数，我认为你不需要辅助助手。我发现在尝试递归逻辑之前识别错误情况很有用。

cond

表达式只关心程序的“快乐路径” -

(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

注：

quotient

返回除法的整数结果。

/

返回一个数字。

注意：使用

Racket > Reindent

选项自动为您格式化源代码。