在我接受到的教育中，递归似乎是一个很神秘的东西。它难以说清，是高级货，像一团迷雾。在高中课外学习的过程中，我一开始没有理解到什么是递归，老师也可能觉得我们比较难以理解，所以后来就没有统一说说。而我也觉得貌似挺难的，也貌似不用也可以，所以就没了回事。后来到了大学，教编程语言的老师居然极度忽视递归，那时的我已经知道递归的重要性，她竟然说了些站不住脚的观点就糊弄过去，说白了，很多都是语法糖衣。

直到看sicp的时候，我或许才真正感受到递归。

首先说明一下，sicp的展开基于一种lisp的方言——scheme语言，它没有所谓的循环语句，因此从语法形式上看，所有的重复做某事的过程都是递归过程。那么按照一般思维，它是否就不存在迭代呢？因为在很多命令式语言诸如C，java等都具有循环语句，所以我们一般写迭代都是用循环语句来写，而不会用函数递归来写，这是比较容易混淆的一点。在scheme语言中，将这种基于具体计算过程的分类，分为递归计算过程和迭代计算过程。我们很多时候都基于语法形式而忽略计算模式来说，其实是不太准确的。

（下面是sicp中文版关于此的一段引文：

当我们说一个过程是递归的时候，论述的是一个语法形式上的事实，说明这个过程的定义中（直接或者间接地）引用了该过程本身。在说某一计算过程具有某种模式时（例如，线性递归），我们说的是这一计算过程的进展方式，而不是相应过程书写上的语法形式。）

一般来说，递归计算过程呈现一种先扩展后收缩的计算模式，即需要解释器（或编译器）维护着某些信息，并会随着扩展而增加。而迭代计算过程并没有任何扩展或收缩，它只需要几个固定的必要的信息。用阶乘函数可以很简洁地阐释：

;递归计算过程

(define (factorial n) 
  (if (= n 1) 
      1 
      (* (factorial (- n 1)) n))) 
 
;迭代计算过程 
(define (fact-iter counter result) 
    (if (= counter 1) 
        result 
        (fact-iter (- counter 1) (* counter result)))) 
(define (factorial1 n) 
  (fact-iter n 1)) 

;递归计算过程
(define (factorial n)
  (if (= n 1)
      1
      (* (factorial (- n 1)) n)))

;迭代计算过程
(define (fact-iter counter result)
    (if (= counter 1)
        result
        (fact-iter (- counter 1) (* counter result))))
(define (factorial1 n)
  (fact-iter n 1))

 

当然，递归计算过程还可以简单分为线性递归计算过程（阶乘）和树形递归计算过程（斐波拉契）。显然，树形递归存在大量的冗余计算，但其特点是简洁。

暂时先说这么多，下一篇分别举几个例子来说明递归计算过程和迭代计算过程。