如何用Racket实现无expt函数的xⁿ递归计算？

先修正你代码里的拼写错误（isinterger?应为integer?），再填充递归分支的逻辑：

(define fast-power
  (lambda (x n)
    (cond
      [(and (number? x) (naturalnumber0? n)) (fast-power-internal x n)]
      [else (error 'fast-power "invalid input.")])))

(define (fast-power-internal x n)
  (cond
    [(= n 0) 1]
    [(even? n) 
     ;; 偶数分支：计算(x^(n/2))²，用let缓存结果避免重复递归
     (let ([half-result (fast-power-internal x (/ n 2))])
       (* half-result half-result))]
    [else 
     ;; 奇数分支：x * x^(n-1)
     (* x (fast-power-internal x (- n 1)))]))

(define (naturalnumber0? n)
  (and (integer? n) (<= 0 n)))

关键逻辑说明 #

• 偶数分支：按照规则xⁿ = (x^(n/2))²，用let存储x^(n/2)的结果，避免两次递归调用同一个表达式，提升计算效率。
• 奇数分支：按照规则xⁿ = x * x^(n-1)，将奇数次幂转化为一次乘上偶数次幂（n-1为偶数），最终会进入偶数分支的快速计算逻辑。

另外，Racket本身内置了nonnegative-integer?，可以直接用它替代你自定义的naturalnumber0?，简化代码：

(define fast-power
  (lambda (x n)
    (cond
      [(and (number? x) (nonnegative-integer? n)) (fast-power-internal x n)]
      [else (error 'fast-power "invalid input.")])))

内容的提问来源于stack exchange，提问作者YdotTdot