尾递归是怎么一回事?什么是尾递归?

zhaoolee

发布于 2018-04-19 17:15:46

2.1K0

发布于 2018-04-19 17:15:46

文章被收录于专栏：木子昭的博客木子昭的博客

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()

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018.03.23 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法