SICP学习笔记（1.2.1 ~ 1.2.2）

                                    SICP学习笔记（1.2.1 ~ 1.2.2）
                                            周银辉

1， 递归过程 和 递归计算过程

在学习SICP前我还没注意过有这样的一个区分，因为我们始终停留在语法表面上的“递归过程（recursive procedure）”，而没有去理解其实质是否是“递归计算过程（recursive process）”。

     

• 递归过程：从语法书写层面上而言的，在过程的定义中，其直接或间接地引用该过程本身。 比如 F{F}或者 F{G{F}}
  

     

• 递归计算过程：从实际运算层面上而言的，一个在语法上按照递归过程书写的函数其在运算时可能是按照递归的方式也可能是按照迭代的方式进行的。这取决于解释器或编译器本身是否有对“递归”进行优化，比如Scheme解释器是“严格尾递归”的, 而C#之类的,即便在语法形式上是"尾递归"的,但其仍然不能被编译成迭代计算过程,当然,你可以使用for,while等.
  

要检测出一个递归过程在计算时到底是按照递归方式还是按照迭代方式进行的，非常容易，只要将其进行深度递归或无限次递归，如果Stack Overflow了，那么是按照递归方式计算的，仅仅是一个死循环似的不停计算但没有栈溢出，那么是按照迭代方式计算的。一般而言函数式编程语言（Scheme，Haskell等）， 会按照迭代方式进行计算；命令式编程语言（C++，C#，Java等）会按照递归方式进行计算。

2，迭代计算过程 和 递归计算过程

根据SICP中所言，迭代计算过程就是那种其状态数目可以用固定数目的状态变量来描述的过程。要理解这个非常简单，我们可以想象一下一个 for 循环 for (int i=0; i i n)
      a
      (G (* i a) (+ i 1) n)))
其中的参数 a 就是我们这里所谓的accumulator parameter， 它累积了每次迭代的结果值并将其作为参数传入到下一次迭代中去。如何累积的呢：新的累计值 = i * 旧的累计值

5，练习 1.9

比较下面两个过程有啥不同：
(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

很简单，对于定义的 过程 ”+“ 而言，第一个是普通的线性递归过程，其计算过程也是递归的； 第二个是尾递归，其计算过程会被Scheme解释器解释成迭代的。

6， 练习1.10

对Ackermann函数求值
在班车上用草稿纸加铅笔计算的，所以这里就没给出程序了
(A 1 10) = 2^10    (A 2 4) = 2^16    (A 3 3) = 2^16  
(define (f n) (A 0 n)) 表示 2n
(define (g n) (A 1 n)) 表示 2^n
(define (h n) (A 2 n)) 表示 2^2^2^... (n 个2)

7，换零钱问题

这个题目非常有意思。注意到下面这句话：
those that do not use any of the first kind of coin, and those that do. Therefore, the total number of ways to make change for some amount is equal to the number of ways to make change for the amount without using any of the first kind of coin, plus the number of ways to make change assuming that we do use the first kind of coin. But the latter number is equal to the number of ways to make change for the amount that remains after using a coin of the first kind。
换零钱的全部方式数，等于完全不使用第一种钱币的方式数目，加上使用了第一种钱币的方式数 （这比较容易理解，就相当于在说，这个世界上的人口数目，等于我不认识的人的总数，加上我认识的人的总数）， 而后一个数目等于去掉一个第一种硬币值后剩下的现金数的换钱方式数（这很明显，因为使用了第一种钱币（假设为a）的换钱方式中，每种方式都包含a，所以可以将a减去）

将其翻译成 C# 代码如下：
        private static readonly int[] FirstDenomination = new[] { 50, 10, 1, 5, 25 };
      

        public static int CountChange(int amount)
        {
            return CountChange(amount, 5);
        }

        public static int CountChange(int amount, int kindsOfCoins)
        {
            if (amount == 0)
            {
                return 1;
            }

            if (amount