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

Question

我正在研究Brain Harvey对计算机编程的结构和解释。我遇到了这个问题，我不知道该怎么做。

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

Answer 1

TL;DR：使用命名let（如果要立即执行递归函数）或rec（如果要保存递归函数以供以后执行）。

---

通常的方法是 letrec ，或者在幕后使用letrec的东西，例如命名 let 或 rec .以下是使用 letrec 的 (factorial 10) 版本：

(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)

Answer 3

这是一个递归函数，它使用 lambda 计算 5 的阶乘

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

当您在Drracket中运行此程序时，您将获得120:)