组成函数的两种方法,效率有什么不同?

让f把一个值转换成另一个值,然后我编写一个函数,它重复转换n次。

我想出了两种不同的方法:

• 一个是显而易见的方式 字面上应用函数n 时代,所以 重复(F,4) 方法 X射线 f(f(f(x)))
• 另一种方式是从 快速供电方法,也就是说 把问题分成两部分 一半大的问题 当n为偶数时。所以 重复(F,4) 方法 X_ G(G(X))。 哪里 g(x)= f(f(x))

起初,我认为第二种方法不会提高效率那么多。一天结束的时候,我们还需要申请N次,不是吗?在上面的例子中, G 仍然会被翻译成 F O F(F O F) 没有进一步的简化,对吗?

但是,当我尝试这些方法时,后一种方法明显更快。

;; computes the composite of two functions
(define (compose f g)
  (lambda (x) (f (g x))))

;; identify function
(define (id x) x)

;; repeats the application of a function, naive way
(define (repeat1 f n)
  (define (iter k acc)
    (if (= k 0)
        acc
        (iter (- k 1) (compose f acc))))
  (iter n id))

;; repeats the application of a function, divide n conquer way
(define (repeat2 f n)
  (define (iter f k acc)
    (cond ((= k 0) acc)
          ((even? k) (iter (compose f f) (/ k 2) acc))
          (else (iter f (- k 1) (compose f acc)))))
  (iter f n id))

;; increment function used for testing
(define (inc x) (+ x 1))

事实上, (repeat2 inc 1000000)0) 比 (重复1 inc 1000000)0) . 我的问题是,第二种方法在哪方面比第一种方法更有效?重新使用相同的函数对象是否保留了存储空间并减少了创建新对象所花费的时间?

毕竟,应用程序必须重复n次,或者用另一种方式说, X((X+1)+1) 不能自动减少到 X(2) 对吧?

我正在运行DRScheme 4.2.1。

非常感谢。