什么是递归

很多人认为函数调用自身就是递归,这虽然从写法(syntactic)上来说没错,但我这里想说的是写法(syntactic)上的递归和演算(evolve)上的递归的区别,SICP中把第一种叫做recursive procedure,第二种叫做recursive process

recursive procedure指的只是一种句法上的写法,recursive process则指的是演算过程中的一种展开方式。两者代表的并不是一样的东西

例如下面就是一个recursive procedure,但演算过程却不是recursive的,而是一个linear iterative process

;linear iteration
(define (sum n rs)
  (if (= n 1)
      (+ 1 rs)
      (sum (- n 1) (+ n rs))))

而下面这个则既是recursive procedure又是recursive process

;linear recursion
(define (sum n)
  (if (= n 1)
      1
      (+ n (sum (- n 1)))))

虽然第一种写法上确实是函数调用自身,符合句法上递归的定义,但其实其本质和各大语言里面的for,while,do...while之流是没区别的,话说回来,scheme仅仅用函数调用机制就实现了各大语言里面的for,while,do...while这些专用的迭代结构的功能,这样看来for,while,do...while确实要被打成syntactic sugar了(题外话,我未来设计的语言要保持simplicity的理念,肯定也是不要这些多余的专用结构的:P