方案:我们如何用lambda编写递归过程？

Question

我正在通过Brain harvey进行计算机编程的结构和解释.我遇到了这个问题,我无法弄清楚如何去做.

我们如何在Scheme中使用lambda编写递归过程？

Answer 1

TL; DR:使用named let(如果您正在立即执行递归函数)或rec(如果要保存递归函数以便以后执行).

通常的方法是letrec使用letrec幕后的东西,比如命名let或者rec.这里有一个版本的(factorial 10)使用letrec:

(letrec ((factorial (lambda (x)
                      (if (< x 1) 1
                          (* (factorial (- x 1)) x)))))
  (factorial 10))

和使用命名相同的东西let:

(let factorial ((x 10))
  (if (< x 1) 1
      (* (factorial (- x 1)) x)))

这里的关键理解是两个版本完全相同.命名let只是一个扩展为letrec表单的宏.因为命名let版本较短,这通常是编写递归函数的首选方法.

现在,你可能会问,如果你想直接返回递归函数对象,而不是执行它,该怎么办？你也可以使用letrec:

(letrec ((factorial (lambda (x)
                      (if (< x 1) 1
                          (* (factorial (- x 1)) x)))))
  factorial)

在那里,也是一个简写,虽然没有使用命名let,而是使用rec:

(rec (factorial x)
  (if (< x 1) 1
      (* (factorial (- x 1)) x)))

在rec这里使用的好处是你可以将函数对象分配给变量并在以后执行它.

(define my-fact (rec (factorial x)
                  (if (< x 1) 1
                      (* (factorial (- x 1)) x))))
(my-fact 10)  ; => 3628800

创建递归函数的理论和"纯粹"方法是使用Y组合子.:-)但是大多数实用的Scheme程序都没有使用这种方法,因此我不再进一步讨论.

Answer 2

无需两次写阶乘体;）

(((lambda (f)
   (lambda (x)
     (f f x)))
 (lambda (fact x)
   (if (= x 0) 1 (* x (fact fact (- x 1)))))) 5)