Lecture 4: Decomposition and abstraction through; introduction to recursion
本课标题的真正翻译为：函数的分解与抽象化及递归介绍
本课基本介绍了如何建立一个函数。这是一个非常简单和基础的知识，我在这里就不重复了。但是初学者时常会出现这样的状况：很多人喜欢滥用函数，在不需要用到函数的时候依然要建立一个函数。那么一下几个注意点就解释了什么时候函数是必要的：
- 函数的最主要作用是把一个程序段储存起来，并使之抽象化。
- 在建好函数之后，我们只需要知道此函数的功能，并不需要知道它具体的运作过程。
- 函数的最主要好处就是避免在不同的地方写重复的程序段，只需调用函数即可。
- 因此，只有在多处需要写同样的程序段时，函数才是必要的。
（注意：在写递归函数的时候，定义函数时会调用此函数本身，这就避免了N次重复程序段，从而使函数变得十分简洁。）
在定义函数时还需要注意的一点是局部变量(Local Variable)和全局变量(Global Variable)的用法。本课仅强调了局部变量的用法，定义函数中所用到的变量仅仅存在于“黑箱”之中。出了这个函数，这些变量就是未定义的(Undefined)。当然，函数中也可以调用全局变量，应该在之后的课程中会提到。这里简要说明就是：在global这个关键词之后写上需要调用的全局变量。
本课举了小学奥数中最经典的“鸡兔同笼”问题，并且用穷举(Brute-force Algorithm)的方法暴力破解。可能在视频中看不清楚，我重新写了一下鸡兔同笼问题的程序，如下：
def solve(numHeads, numLegs):
""" this function is to calculate numbers of chickens and pigs """
test = False
for numChickens in range(0, numHeads + 1):
numPigs = numHeads - numChickens
if 2 * numChickens + 4 * numPigs == numLegs:
test = True
return numChickens, numPigs
if not test:
return None, None
def Farmyard():
""" this function is to get inputs from users and print solutions """
numHeads = int(raw_input("Number of heads is: "))
numLegs = int(raw_input("Number of legs is: "))
numChickens, numPigs = solve(numHeads, numLegs)
if numChickens == None and numPigs == None:
print "No solution"
else:
print "Number of chickens is:", numChickens
print "Number of pigs is:", numPigs
本课的第二部分简单介绍了递归式，这里涉及的仅仅是最基本的递归式，例如：U(n) = U(n-1) + U(n-2)。这是一个斐波那契数列的递归式。当然，U(0) = 1， U(1) = 1。
由此，我们可以写出斐波那契数的递归解法，程序如下：
def Fibonacci(n):
if n == 1 or n == 0:
return 1
else:
return Fibonacci(n - 1) + Fibonacci(n - 2)
我们发现：在定义这个函数中，我们又调用了这个函数本身，这就达到了递归的效果。
这仅仅是一个非常简单的例子，我们还可以任意变换一下这个递归式，例如：T(0) = 0, T(1) = 0, T(2) = 0, T(n) = T(n-1) + T(n-3) + 3
那么我们可以用一下程序解出T(n)：
def T(n):
if n == 0 or n == 1 or n == 2:
return 0
else:
return T(n-1) + T(n-3) + 3
这就构成了一个最基本的解递归的程序结构。
总结：本课最主要的就是递归入门，没有学过递归的需要来这里看一下。
