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

Question

问题是找到一个数x的x^n的n次方，其中n是一个正整数。下面两段代码有什么区别。他们都产生相同的结果。

这是第一个的代码：

(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)来计算结果。

维基百科有一些detailed analysis of this。