如何在 Lisp(scheme) 中编写幂函数？我这里的程序有什么问题？

Question

(define (pow b n) 
    "YOUR-DOC-HERE"
    (cond ((= n 0) 1)
          ((even? n) (pow (pow b (/ n 2)) 2))
          ((odd? n) (* b (pow (pow b (/ (- n 1) 2)) 2)))))


(define (pow b n) 
    "YOUR-DOC-HERE"
    (cond ((= n 0) 1)
          ((even? n) (* (pow b (/ n 2)) (pow b (/ n 2))))
          ((odd? n) (* b (pow b (/ (- n 1) 2)) (pow b (/ (- n 1) 2))))))

这是我的代码的两个版本，用于具有对数效率的幂函数。但是，第一个函数会出现 maximum recursion depth exceeded 错误，第二个函数虽然有效，但似乎没有达到所需的效率。我是 Scheme 的新手，我想知道这些实现有什么问题？

Answer 1

您的第一个版本使用自身对每个值求平方，这在 even? 子句中创建了一个无限循环。

您的第二个版本在每个子句中调用 pow 两次，这会反转对数算法的任何增益。

您可以使用 let 修复它，如下所示：

(define (pow b n)
  "Recursive power in logarithmic depth."
  (let ((square (lambda (x) (* x x))))
    (cond ((= n 0) 1)
          ((even? n) (square (pow b (/ n 2))))
          ((odd? n) (* b (square (pow b (/ (- n 1) 2))))))))

或者像这样：

(define (pow b n)
  "Recursive power in logarithmic depth."
  (cond ((= n 0) 1)
        ((even? n)
         (let ((x (pow b (/ n 2))))
           (* x x)))
        ((odd? n)
         (let ((x (square (pow b (/ (- n 1) 2)))))
           (* b x x)))))

如何在 Lisp(scheme) 中编写幂函数？我这里的程序有什么问题？

How to write a power function in Lisp(scheme)? What's wrong with my program here?

lisp

algorithm

scheme

function