递归

递归

下面这个函数大家学过数学的都知道吧，阶乘的函数定义。

递归.jpg

转换

我们将上面的数学表达式转换成下面的代码

def factorial(n):

 if n == 0:

 return 1

 return n * factorial(n-1)

print factorial(5)

关注点

1. 基线条件

递归就是函数自己调用自己，但函数什么时候结束，要有一个条件，不然就会一直递归知道栈溢出。上面的基线条件是n == 0

2. 递归条件

递归条件就是需要调用自身的地方。上面递归条件是 n * factorial(n-1)

## 栈

栈也是一种数据结构。还有一种是堆。栈就像一口井一样先进去的后出来，比如我们声明的函数，在执行的时候就会把它加入到栈中，当函数执行完之后再把它pop出去，销毁掉。如果函数中还有其他函数，那么就会一层一层的压入到栈中，只有内层函数执行完后才会将这个函数销毁掉。栈是有一定大小的，如果一直push到栈中，那么栈会溢出。这也是为什么递归一定要找到基线条件的原因，防止死循环。如果你不明白栈，你可以好好去网上找些资料来学习。

递归优化

我们看到上面是因为内部函数因为没有立即返回，一直等到内层函数执行，知道n=0才返回。其实我们可以使用下面的代码进行优化，优化的效果很明显。这里你或许可以明白一些。尾递归

def factorial(n, total=1):

 if n == 0:

 return total

 return factorial(n-1, total * n)

print factorial(5)

更加深入

如果你编写了这样一个函数去计算阶乘，比如我输入5那么他就给我返回120， 对于这个函数来说，我们输入一定结果就一定，也就是参数 -> 函数 -> 输出这个过程。那么我们可以写一个带有缓存的函数，如果我输入5那么我先去缓存中查，如果有值我们直接返回，没有值在进行计算。如果你看了上面介绍的尾递归的话，里面就介绍柯里化，就是将多个参数转换成单个参数调用。其实我们还可以使用其中特性捕获上下文。

def memoried(fn):

 def factorial (args, cachedMap={'args': None, 'result': None}):

 if cachedMap['args'] == args:

 return cachedMap['result']

 else:

 result = fn(args)

 cachedMap['args'] = args

 cachedMap['result'] = result

 return result

 return factorial 

def factorial(n, total=1):

 if n == 0:

 return total

 print n

 return factorial(n-1, total * n)

cachedFactorial = memoried(factorial)

print cachedFactorial(100)

总结

• 使用递归一定要注意基线条件和递归条件

• 进行尾调优化

• 尝试使用缓存来减轻每次的查找，这种一定要是纯函数（唯一输入对应唯一输出）