理解 Scheme 中的 repeat 函数

Question

Scheme中重复一个函数的代码如下：

(define (repeat f n)
  (if (= n 1)
      f
      (lambda (x) (f ((repeat f (- n 1)) x)))))

但我不明白这里的递归如何与 lambda(x) 等一起工作。

有人可以用 (repeat f 3) 这样的例子来解释吗？

谢谢

Answer 1

需要注意的是，这个 repeat 函数实际上并没有调用 f n 次。它 returns 一个将调用 f n 次的新函数。您可以在基本情况下看到这一点：当 (= n 1) 时，它只是 returns f，它不会执行 (f).

(repeat f (- n 1)) 递归调用 repeat 来获得一个少调用 f 一次的函数。 lambda 然后用于构造一个调用此新函数的新函数，然后调用 f 进行总 n 次调用。

Answer 2

使用替代方法并“向上”工作：

(repeat f 1)
--> f

如果 f 是一元函数，

等同于 (lambda (x) (f x))。

然后，

(repeat f 2)
--> (lambda (x) (f ((repeat f 1) x)))
--> (lambda (x) (f (f x)))

和

(repeat f 3)
--> (lambda (x) (f ((repeat f 2) x)))
    [through name change in the "inner" lambda]
--> (lambda (x) (f ((lambda (y) (f (f y))) x)))
    [through ((lambda (y) (f (f y))) x) --> (f (f x))]
--> (lambda (x) (f (f (f x))))

理解 Scheme 中的 repeat 函数

understanding the repeat function in Scheme

scheme