递归
2018-01-20 本文已影响0人
张义飞
递归
下面这个函数大家学过数学的都知道吧，阶乘的函数定义。
递归.jpg
转换
我们将上面的数学表达式转换成下面的代码
def factorial(n):
if n == 0:
return 1
return n * factorial(n-1)
print factorial(5)
关注点
- 基线条件
递归就是函数自己调用自己，但函数什么时候结束，要有一个条件，不然就会一直递归知道栈溢出。上面的基线条件是n == 0
- 递归条件
递归条件就是需要调用自身的地方。上面递归条件是 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)
总结
-
使用递归一定要注意基线条件和递归条件
-
进行尾调优化
-
尝试使用缓存来减轻每次的查找，这种一定要是纯函数（唯一输入对应唯一输出）
