50% 的算法问题都能通过递归来解决, 倒不是说递归本身有多厉害, 只是说明递归的思想让很多复杂的问题变得简单! 啥? 了解数据结构的人都知道, 树结构本身就是用递归定义的, 所以解决树相关的问题会优先考虑递归
什么是尾递归?
众所周知, 递归会记录上一个函数的调用状态, 造成大量的资源占用, 为了尽量减少资源的占用, 有了为递归的玩法, 就是把递归操作放到 return 内, 由于 return 是函数的最后一句, 所以, 就可以减少记录函数体的空间
两种递归方式
普通递归写法
- function recursion(num){
- new_num = num + 1
- if (num>= 20000){
- return
- }
- console.log("普通递归 | 第",new_num,"次调用")
- recursion(new_num)
- }
- recursion(1)
尾递归写法 (直接将函数调用 return 出去 )
- // 尾递归
- function recursion2(num){
- new_num = num + 1
- if (num>= 20000){
- return
- }
- console.log("尾递归 | 第",new_num,"次调用")
- return recursion2(new_num)
- }
- recursion2(1)
尾递归节约了递归过程中压栈的内存消耗, 但这种玩法并不能突破递归栈的限制 (python 约为 1000 次, Chrome js 环境约为 20000 次), 函数 recursionreturn 自身之后 并没有析构释放空间,
为了验证以上说法, 这里用 Python 举一个例子 (js 的析构很难写, 还是 python 好用...)
析构时机
- class Recursion(object):
- def __init__(self, num):
- self.num = num
- print("对象 obj",self.num, "建立")
- def __del__(self):
- print("对象 obj", self.num-1, "析构")
- # 尾递归
- def add(self):
- print(">> 尾递归 | 第",self.num,"次")
- self.num += 1
- if (self.num>10):
- return
- else:
- return Recursion(self.num).add()
- # 正常递归
- def add2(self):
- print(">> 正常递归 | 第",self.num,"次递归")
- self.num += 1
- if (self.num>10):
- return
- else:
- Recursion(self.num).add2()
- def main():
- # 尾递归
- recu = Recursion(1)
- recu.add()
- # 正常递归
- recu2 = Recursion(1)
- recu2.add2()
- if __name__ == '__main__':
- main()
来源: http://www.jianshu.com/p/136a4323cf96