这两个递归函数有什么区别

Question

问题是找到数字x的x^n的n次方，其中n i是正整数。下面的两段代码有什么不同。它们都产生了相同的结果。

这是第一个的代码：

(define (power x n)
  (define (square n) (* n n))
  (cond ((= n 1) x)
        ((even? n)
         (square (power x (/ n 2))))
        (else 
         (* (power x (- n 1)) x))))

这是第二个：

(define (power x n)
  (if (= n 1)
      x 
      (* x (power (- n 1) x))))

Answer 1

区别在于两种算法运行所需的时间。

第二种方法更简单，但效率更低：它需要O(n)乘法来计算x^n。

第一种算法被称为平方和乘法算法。本质上，它使用指数的二进制表示，并使用身份

x^(ab) = ((x^a)^b)
x^(a+b) = (x^a)(x^b)

以计算结果。它只需要O(log n)的乘法运算就可以计算出结果。

维基百科对此有一些详细的分析。