1

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

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

4

3 回答 3

8

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

通常的方法是 with ，或者在幕后letrec使用 a 的东西，比如 named或。这是using的一个版本：letrecletrec(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)

这里也有一个简写，虽然没有使用 named 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 程序都没有使用这种方法，所以我不会进一步讨论它。

于 2012-06-27T17:08:47.450 回答
5

不需要写两次阶乘体；）

(((lambda (f)
   (lambda (x)
     (f f x)))
 (lambda (fact x)
   (if (= x 0) 1 (* x (fact fact (- x 1)))))) 5)
于 2012-06-28T10:30:07.433 回答
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 :)

于 2012-06-27T17:48:34.897 回答