recursion - 乔尔·斯波尔斯基 (Joel Spolsky) 在变量值不同时变化的悖论中是什么意思？

Question

我读了 The perils of Java Schools大约 8 个月前，从那时起，我一直将它用作我应该很快学习的内容的 list 。我明白他所说的大部分内容。

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

in a purely functional program, the value of a variable never changes, and yet, it changes all the time! A paradox!

我从中得到的(如果我错了，请原谅我)是他在谈论递归，但递归似乎是一个太简单的概念。这是我的思路:

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

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

Answer 1

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

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

考虑一个 greatest common divisor功能:

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

在这里，每次除法的余数 x来自 y非零，它(尾)递归调用 gcd再次，在这个新电话中， x和 y值(value)观不同。 (特别是， y 值每次迭代都会变小，最终导致基本情况是 x 正好除以 y，即使 y 必须为 1 才能发生这种情况。)

这是纯函数递归的另一种情况(这次不是尾递归，虽然 it's possible to implement with tail recursion 也是)，用于实现合并两个排序的数字列表的算法:

(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非空，我们递归到另一个调用 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))))))

这是 divide-and-conquer algorithm 的经典示例.每次列表有 2 个或更多元素时，将列表分成左右两半，递归到每一半，然后将已排序的两半合并在一起。