每一个计算机程序都是现实中或者精神中的某一个过程的一个模型
SICP 序
在这一层次的课程里,最基本的材料并不是特定的程序设计语言语法,不是有效计算某种功能的巧妙算法,也不是算法的数学分析或者计算的本质,而是一些能够用于控制大型软件系统的智力复杂性的技术
SICP 前言

计算机程序中对象可以大体分为两类:数据和过程。数据是那些需要去操作的东西,过程则是具体操作的指令。要求解复合过程的结果需要先得到子过程的结果,求子过程的结果需要得到子过程的子过程的结果,一次类推直到某一层子过程是最基本的表达式得到求值结果,这就是递归。

递归的简单应用,欧几里得算法求最大公约数

1
2
3
4
5
6
7
func gcd(x x: Int, y: Int) -> Int {
if y == 0 {
return x
} else {
return gcd(x: y, y: x%y)
}
}

Fibonacci 数列求值

Fibonacci 数列的定义本身就是递归的,可以很自然的写成:

1
2
3
4
5
6
7
func fib1(n: Int) -> Int {
switch n {
case 0: return 0
case 1: return 1
default: return fib1(n-1) + fib1(n-2)
}
}

这个方法在求解的过程中所需的步数随着n的增加增长阶是O(2^n),仔细观察递归过程中同样的值重复计算了很多次,于是可以优化在计算过程中把结果保留下来,这种做法被归类为 Dynamic Programming 方法,没想到的是中文翻译居然是动态规划

1
2
3
4
5
6
7
8
9
10
func fib2(n: Int) -> Int {
var tmpArray = [0, 1]
func fib2Inside(m: Int) -> Int {
if m >= tmpArray.count {
tmpArray.append(fib2Inside(m-1) + fib2Inside(m-2))
}
return tmpArray[m]
}
return fib2Inside(n)
}

在递归中有一类尾递归,可能也可以叫伪递归,是在递归的过程中保留全部状态,其实就是一种迭代,这种计算方式要快于一般的递归。如果递归解决的思路是从后往前的,那么迭代刚好相反是从前往后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func fib3(n: Int) -> Int {
func fibIter(a: Int, b: Int, count: Int) -> Int {
if count == 0 {
return b
} else {
return fibIter(a+b, b: a, count: count-1)
}
}
return fibIter(1, b: 0, count: n)
}
func fib4(n: Int) -> Int {
guard n > 1 else {
return n
}
var count = n, x = 0, y = 1
repeat {
(x, y) = (y, x+y)
count--
} while count > 1
return y
}

使用迭代的方式计算,计算步数相对于n的增长阶是O(n),如果要继续精简这个计算过程发现每次迭代的变化都是一样的,那么将两次迭代的过程合为一次,那么所需步骤数就可以减半,最后得到时间复杂度为 O(logn) 的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func fib5(n: Int) -> Int {
guard n > 1 else {
return n
}
var count = n+1, x = 0 , y = 1
if count % 2 != 0 {
(x, y) = (y, x+y)
count--
}
var countHalf = count/2
repeat {
(x, y) = (x+y, x+2*y)
countHalf--
} while countHalf > 1
return y
}

零钱组合问题

给定一个金额 N,计算有多少种不同的零钱组合方式。这个问题应用递归就没有上一个那么直观,但只需要找出分解问题并且子问题和问题本身是同一类问题的方式。将换算组合个数分为两部分,没有一种面值的组合个数加上至少有一张这种面值的组合个数

1
2
3
4
5
6
7
func cc1(amount: Int, denomination: Array<Int>) -> Int {
if amount < 0 || denomination.count == 0 { return 0 }
if amount == 0 { return 1 }
var deno = denomination
deno.removeLast()
return cc1(amount - denomination[denomination.count-1], denomination: denomination) + cc1(amount, denomination: deno)
}

在 Dynamic Programming 的思想下优化,用一个表的行列代表金额数和不同面值个数,在表中存储计算过的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func cc2(amount: Int, denomination: Array<Int>) -> Int {
var table = Array(count: amount+1, repeatedValue: Array(count: denomination.count+1, repeatedValue: -1))
var i = 0, j = 0
while j < denomination.count+1 {
table[0][j] = 1
j++
}
while i < amount+1 {
table[i][0] = 0
i++
}
func cc2Inside(amount2: Int, denomination2: Array<Int>) -> Int {
if amount2 < 0 {
return 0
}
if table[amount2][denomination2.count] == -1 {
var deno = denomination2
deno.removeLast()
table[amount2][denomination2.count] = cc2Inside(amount2-denomination2[denomination2.count-1], denomination2: denomination2) + cc2Inside(amount2, denomination2: deno)
}
return table[amount2][denomination2.count]
}
return cc2Inside(amount, denomination2: denomination)
}

这个问题也可以迭代,但是我是没能想出来,搜到的一种做法是

1
2
3
4
5
6
7
8
9
10
func cc3(amount: Int, denomination: Array<Int>) -> Int {
var table = Array(count: amount+1, repeatedValue: 0)
table[0] = 1
for(var i=0; i<denomination.count; i++) {
for(var j=denomination[i]; j<=amount; j++) {
table[j] += table[j-denomination[i]]
}
}
return table[amount]
}

显然相比之下递归的代码更容易读懂