编程语言

SICP笔记（二）

The ability to visualize the consequences of the actions under consideration is cruial to becoming an expert programmer,just as it is in any synthetic,creative activity.

线性递归 · 线性迭代

1
2
3
4
5
;;; 阶乘的线性递归实现
(define (factorial n)
  (if (= n 0)
    1
    (* n (factorial (- n 1)))))

通过代换模型，一个线性递归过程是一个先展开后收缩的形状，当计算过程建立一个延迟操作的链条时，过程展开，而这些操作的执行就表现为过程的收缩。执行递归过程需要解释器跟踪维持这些延迟操作的轨迹。

1
2
3
4
5
6
7
8
9
;;; 阶乘的线性迭代实现
(define (factorial n)
  (fact-iter 1 1 n))
(define (fact-iter product counter max-count)
  (if (> counter max-count)
    product
    (fact-iter (* counter product)
           (+ counter 1)
           max-count)))

与线性递归相比，线性迭代并没有展开或者收缩的形状。一个迭代计算过程的状态可以用固定数目的状态变量来描述，同时有一套固定的规则用来描述当计算过程从一个状态到下一状态时，变量应该如何变化，并还可能有一个用来指明结束条件的结束测试。
如果我们中途打断计算过程，然后向解释器提供程序变量的值，迭代过程就能唤醒，但递归过程却不能，这是因为递归过程有一些由解释器维持的隐藏信息，并不存在于程序变量之中。

recursive process · recursive procedure

当我们描述一个程序是递归的时，我们是指这个程序的定义中引用了它自己的语法事实；当说某个计算过程是递归时，指这个过程的进展方式，而不是指写程序时的语法形式。如，上文的fact-iter是一个递归程序，计算时却产生一个迭代过程。
现今的大多数语言的实现设计中，对于任何递归程序的解释，消耗的内存总与程序调用的次数成正比，哪怕当计算过程从原理上看是迭代的。因此，这些语言要描述迭代过程要通过特殊的循环结构。

树形递归

1
2
3
4
5
6
;;; Fibonacci数列的递归实现
(define (fib n)
  (cond ((= n 0) 0)
      ((= n 1) 1)
      (else (+ (fib (- n 1))
               (fib (- n 2))))))

就像(fib n)的计算过程，树形递归的进展过程像一棵树。树形递归过程使用大量的计算步骤，随着输入成指数增长，进行大量的重复计算，效率低，但思路清晰直接，同时是处理层次结构数据的好工具。

增长的阶

在计算机科学中，算法分析(Analysis of algorithm)是分析执行一个给定需要消耗的计算资源数量（例如计算时间，存储器使用等）的过程。算法的效率或复杂度在理论上表示为一个函数。其定义域是输入数据的长度（通常考虑任意大的输入，没有上界），值域通常是执行步骤数量（时间复杂度）或者存储器位置数量（空间复杂度）。
增长的阶只是提供了一种对计算过程行为的一种很粗略的描述，并不能精准地描述计算过程中资源的消耗，但却可以提供了一种有效的方法预期当我们改变问题的规模时，过程的行为将如何变化。

求幂

计算过程线性递归线性迭代连续平方
时间复杂度O(n)O(n)O(log n)
空间复杂度O(n)O(1)O(log n)

素数检测

寻找因子：对于数n，从2开始寻找最小整数因子。如若最小整数因子是n，则为素数；否则不是。
费马检测：通过费马检测的数，不一定是素数，无法通过的一定不是素数。能骗过费马检测的数称为卡迈克尔数(Carmichael numbers)，卡迈克尔数数量非常少。像这种存在任意小概率出错机会的算法称为概率算法(probabilistic algorithms)。

Testing · Debugging

Testing

1
2
3
4
;;; testing in racket
(require htdp/testing) ;导入库
(check-expect <funct-call> <expected-output>)
(generate-report)


Debugging

1
2
3
;;; debugging in racket
(require racket/trace)
(trace fac)


有话说

语言是为了分歧而存在的，真正相知的两个人，无需多说。

习题解答：传送门