2

大约 8 个月前，我阅读了 Java Schools 的危险，从那时起，我一直将它用作我应该很快学习的东西的清单。我理解他所说的大部分内容。

然而，这部分我不太确定：

在纯函数式程序中，变量的值永远不会改变，但它一直在改变！一个悖论！

我从中得到的（如果我错了，请原谅我）是他在谈论递归，但递归似乎是
一个过于简单的概念。这是我的思路：

(define (tail-rec n) 
  (if (= n 1) 
    (display "Done!") 
    (begin 
       (display n)
       (newline) 
       (tail-rec (- n 1)))))

n当您查看输出的内容时，尾递归函数中的值tail-rec还没有改变，您会发现它实际上发生了变化。此外，由于函数本身不会改变
任何变量的状态，这意味着它是纯函数式的。
苏……
我说得对吗？
这就是乔尔所说的吗？如果没有，请纠正我。

4

1 回答 1

3

为了回答您的问题，Joel 的文章确实指的是这种情况下的递归。

但是，您的代码实际上并不是纯功能的，因为display并且newline具有副作用。因此，我将切入正题，为您提供一些纯函数递归代码的切实示例。

考虑一个最大公约数函数：

(define (gcd x y)
  (if (zero? y)
      x
      (gcd y (modulo x y))))

在这里，每次除以的余数x非零y时，它（尾）递归地gcd再次调用，在这个新调用中，x和y值是不同的。（特别是，每次迭代该值都会变小，最终导致精确除法y的基本情况，即使必须为 1 才能发生这种情况。）xyy

这是纯函数递归的另一种情况（这次不是尾递归，尽管也可以使用尾递归来实现），用于实现合并两个排序的数字列表的算法：

(define (merge lhs rhs)
  (cond ((null? lhs) rhs)
        ((null? rhs) lhs)
        ((< (car rhs) (car lhs))
         (cons (car rhs) (merge lhs (cdr rhs))))
        (else
         (cons (car lhs) (merge (cdr lhs) rhs)))))

同样，每当我们处理lhs和rhs都是非空的情况时，我们会递归到另一个调用 into merge，其中一个列表在每次调用中都更短，最终我们会遇到一个基本情况，其中一个列表是空的.

这个合并函数可以用来实现合并排序：

(define (mergesort lst)
  (let ((len (length lst)))
    (if (< len 2)
        lst
        (let-values (((lhs rhs) (split-at lst (quotient len 2))))
          (merge (mergesort lhs) (mergesort rhs))))))

这是分治算法的经典例子。每次列表有 2 个或更多元素时，将列表分成左右两半，递归到每一半，然后将排序后的两半合并在一起。

于 2013-08-11T08:37:28.447 回答