递归
如果用上面的做递归的定义，总感觉有点调侃，来个严肃的(选自维基百科)：
递归（英语：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。
根据斐波那契数列的定义，可以直接写成这样的斐波那契数列递归函数。
#!/usr/bin/env python
# coding=utf-8
def fib(n):
"""
This is Fibonacci by Recursion.
"""
if n==0:
return 0
elif n==1:
return 1
else:
return fib(n-1) + fib(n-2)
if __name__ == "__main__":
f = fib(10)
print f
fib(n-1) + fib(n-2)就是又调用了这个函数自己，实现递归。为了明确递归的过程，下面走一个计算过程（考虑到次数不能太多，就让n=3）
1. n=3,fib(3)，自然要走return fib(3-1) + fib(3-2)分支
2. 先看fib(3-1),即fib(2)，也要走else分支，于是计算fib(2-1) + fib(2-2)
3. fib(2-1)即fib(1)，在函数中就要走elif分支，返回1，即fib(2-1)=1。同理，容易得到fib(2-2)=0。将这两个值返回到上面一步。得到fib(3-1)=1+0=1
4. 再计算fib(3-2),就简单了一些，返回的值是1，即fib(3-2)=1
5. 最后计算第一步中的结果：fib(3-1) + fib(3-2) = 1 + 1 = 2，将计算结果2作为返回值
从而得到fib(3)的结果是2。
从上面的过程中可以看出，每个递归的过程，都是向着最初的已知条件a0=0,a1=1方向挺近一步，直到通过这个最底层的条件得到结果，然后再一层一层向上回馈计算机结果。
其实，上面的代码有一个问题。因为a0=0,a1=1是已知的了，不需要每次都判断一边。所以，还可以优化一下。优化的基本方案就是初始化最初的两个值。
#!/usr/bin/env python
# coding=utf-8
"""
the better Fibonacci
"""
meno = {0:0, 1:1} #初始化
def fib(n):
if not n in meno: #如果不在初始化范围内
meno[n] = fib(n-1) + fib(n-2)
return meno[n]
if __name__ == "__main__":
f = fib(10)
print f
#运行结果
$ python 20402.py
55
几个特殊的函数
filter、map、reduce、lambda、yield
lambda
例子：讲list中每个数字增加3，并输出到新的list中
>>> def add(x): #定义一个函数，将输入的变量增加3,然后返回增加之后的值
... x += 3
... return x
...
>>> numbers = range(10)
>>> numbers
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] #有这样一个list，想让每个数字增加3,然后输出到一个新的list中
>>> new_numbers = []
>>> for i in numbers:
... new_numbers.append(add(i)) #调用add()函数，并append到list中
...
>>> new_numbers
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
在这个例子中，add()只是一个中间操作。当然，上面的例子完全可以用别的方式实现。比如：
>>> numbers = range(10)
>>> new_numbers = [ i+3 for i in numbers ]
>>> new_numbers
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
使用lambda实现，如下：
# 简单的例子
>>> lam = lambda x:x+3
>>> lam(1)
4
>>> lam(2)
5
>>> lam = lambda x:x*3
>>> lam(2)
6
>>> lam = lambda x,y:x*y
>>> lam(2,3)
6
# 实现上述方法：
>>> numbers = range(10)
>>> lam = lambda x:x+3
>>> n2 = []
>>> for i in numbers:
... n2.append(lam(i))
...
>>> n2
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
通过上面例子，总结一下lambda函数的使用方法：
- 在lambda后面直接跟变量
- 变量后面是冒号
- 冒号后面是表达式，表达式计算结果就是本函数的返回值
lambda arg1, arg2, ...argN : expression using arguments
要特别提醒看官：虽然lambda 函数可以接收任意多个参数 (包括可选参数) 并且返回单个表达式的值，但是lambda 函数不能包含命令，包含的表达式不能超过一个。不要试图向 lambda 函数中塞入太多的东西；如果你需要更复杂的东西，应该定义一个普通函数，然后想让它多长就多长。
就lambda而言，它并没有给程序带来性能上的提升，它带来的是代码的简洁。比如，要打印一个list，里面依次是某个数字的1次方，二次方，三次方，四次方。用lambda可以这样做：
>>> lamb = [ lambda x:x,lambda x:x**2,lambda x:x**3,lambda x:x**4 ]
>>> for i in lamb:
... print i(3),
...
3 9 27 81
map
map()是python的一个内置函数，它的基本样式是：
map(func,seq)
func是一个函数，seq是一个序列对象。在执行的时候，序列对象中的每个元素，按照从左到右的顺序，依次被取出来，并塞入到func那个函数里面，并将func的返回值依次存到一个list中。
>>> items = [1,2,3,4,5]
>>> squared = []
>>> for i in items:
... squared.append(i**2)
...
>>> squared
[1, 4, 9, 16, 25]
>>> def sqr(x): return x**2
...
>>> map(sqr,items)
[1, 4, 9, 16, 25]
>>> map(lambda x: x**2, items)
[1, 4, 9, 16, 25]
>>> [ x**2 for x in items ] #这个我最喜欢了，一般情况下速度足够快，而且可读性强
[1, 4, 9, 16, 25]
理解要点：
- 对iterable中的每个元素，依次应用function的方法（函数）（这本质上就是一个for循环）。
- 将所有结果返回一个list。
- 如果参数很多，则对那些参数并行执行function。
例如:
>>> lst1 = [1,2,3,4,5]
>>> lst2 = [6,7,8,9,0]
>>> map(lambda x,y: x+y, lst1,lst2) #将两个列表中的对应项加起来，并返回一个结果列表
[7, 9, 11, 13, 5]
请看官注意了，上面这个例子如果用for循环来写，还不是很难，如果扩展一下，下面的例子用for来改写，就要小心了：
>>> lst1 = [1,2,3,4,5]
>>> lst2 = [6,7,8,9,0]
>>> lst3 = [7,8,9,2,1]
>>> map(lambda x,y,z: x+y+z, lst1,lst2,lst3)
[14, 17, 20, 15, 6]
reduce
>>> reduce(lambda x,y: x+y,[1,2,3,4,5]
15
原来map是上下运算，reduce是横着逐个元素进行运算。
为了锻炼思维，看这么一个问题，有两个list，a = [3,9,8,5,2],b=[1,4,9,2,6],计算：a[0]b[0]+a[1]b[1]+...的结果。
>>> a
[3, 9, 8, 5, 2]
>>> b
[1, 4, 9, 2, 6]
>>> zip(a,b) #复习一下zip，下面的方法中要用到
[(3, 1), (9, 4), (8, 9), (5, 2), (2, 6)]
>>> sum(x*y for x,y in zip(a,b)) #解析后直接求和
133
>>> new_list = [x*y for x,y in zip(a,b)] #可以看做是上面方法的分布实施
>>> #这样解析也可以：new_tuple = (x*y for x,y in zip(a,b))
>>> new_list
[3, 36, 72, 10, 12]
>>> sum(new_list) #或者:sum(new_tuple)
133
>>> reduce(lambda sum,(x,y): sum+x*y,zip(a,b),0) #这个方法是在耍酷呢吗？
133
>>> from operator import add,mul #耍酷的方法也不止一个
>>> reduce(add,map(mul,a,b))
133
>>> reduce(lambda x,y: x+y, map(lambda x,y: x*y, a,b)) #map,reduce,lambda都齐全了，更酷吗？
133
filter
通过下面代码体会：
>>> numbers = range(-5,5)
>>> numbers
[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4]
>>> filter(lambda x: x>0, numbers)
[1, 2, 3, 4]
>>> [x for x in numbers if x>0] #与上面那句等效
[1, 2, 3, 4]
>>> filter(lambda c: c!='i', 'qiwsir') #能不能对应上面文档说明那句话呢？
'qwsr' #“If iterable is a string or a tuple, the result also has that type;”
