Scheme列表交集函数优化：如何避免重复递归调用？

你之前的写法错误在于，let里绑定的appel是一个字面量列表'(intersection (cdr l1) l2)，而不是递归调用的实际结果。直接使用这个字面量或者eval都无法正确工作——eval会在全局环境中求值，无法获取当前函数的参数上下文，而且完全没必要用它。

正确的做法是在let中直接对递归调用求值并绑定变量，代码如下：

(define (intersection l1 l2)
  (if (null? l1) '()
      (let ((appel (intersection (cdr l1) l2)))
        (if (member (car l1) l2)
            (cons (car l1) appel)
            appel))))

如果想让代码可读性更好，可以给变量换个更语义化的名字，同时用cond简化嵌套的if：

(define (intersection l1 l2)
  (cond ((null? l1) '())
        (else
         (let ((rest-intersection (intersection (cdr l1) l2)))
           (if (member (car l1) l2)
               (cons (car l1) rest-intersection)
               rest-intersection)))))

这样变量只会被求值一次，既消除了重复代码，又保证递归逻辑正常运行。

内容的提问来源于stack exchange，提问作者david