文章概述

递归算法和尾递归概述
递归算法的优化

递归算法

介绍：递归算法是计算机编程领域非常重要的一种算法，采用分而治之的思想，将大问题小问题化，复杂问题简单化，但是使用不当时，会产生无限循环或者效率低下的后果。熟练掌握递归算法的技巧和思想，能很大的提升代码质量。那么什么是递归呢，举个例子来讲，想求1000的阶乘，只需要求999的阶乘乘以1000，依次类推，把问题分化成小块。简而言之，递归算法的思想是调用本身来求解。
另外还有一个尾递归的概念：进入下一个函数不再需要上一个函数的环境，如：

def cal(n):
    print(n)
    return cal(n+1)  # return代表函数的结束

尾递归的效率比非尾递归的高，操作系统使用堆栈来处理递归，非尾递归，要在堆栈上新建一个栈帧来存储当前调用函数的数据，比如变量、返回地址等。每递归一次就新建一个栈帧，如果处理很深的递归，很有可能造成栈溢出。而尾递归，递归时，它不会去新建一个栈帧，而是用当前函数的信息覆盖掉栈顶栈帧中的信息。是因为递归语句位于函数的最后，不再需要上一个函数的环境。这样省去了创建栈帧的开销且可避免栈溢出。

斐波那契数列：1,1,2,3,5,8,13,21,34....
利用递归求斐波那契数列，python实现：

def test(n):
   """递归函数输出斐波那契数列"""
   if n <= 2:
       return 1
   else:
       return(test(n-1) + test(n-2))

但是发现一个问题，简单虽简单，但是当n大一点的时候，需要很长时间才能出运行结果，效率极其低下，根本不能用于解决实际问题，那么是什么原因导致的呢，经过思考得知：做了大量的重复工作，分析如下：求test(20)时，先求test(19)和test(18)，求test(19)和test(18)时，要求得test(18)，test(17)和test(19)，test(18)，依次类推，做了大量的重复运算。

递归缓存优化

既然已经知道造成效率低下的原因了，那么优化就很简单了，其中之一，就是加缓存，每次计算后都加入缓存，这样就可以避免重复计算，大大提升效率
python实现：

def optimize(n, cache=None):
   """优化递归函数"""
   if cache is None:
       cache = {}
   if n in cache:
       return cache[n]
   if n <= 2:
       return 1
   else:
       cache[n] = (optimize(n-1,cache) + optimize(n-2,cache))
       return cache[n]

经过测试，效率提升了很多，实际上是通过牺牲空间的方式换取效率，但是可能会出现一个问题，当数据量特别大的话，内存消耗会很大。
另外也可以使用@functools.lru_cache装饰器优化耗时久的递归。