递归函数的空间复杂度实例剖析

运行时栈类c语言的函数调用原理都是如此递归函数的空间复杂度是由递归的深度来决定的。当程序运行时运行时栈存储着程序的函数调用。每当有一个函数被调用时就会有一个新的栈帧被压入栈顶每当一个函数调用完成时就会有一个栈帧弹出栈顶。每一个栈帧中存储函数调用的基本信息其中包含函数参数和局部变量。对于一般函数运行时栈使用的空间与直接申请的空间相比较小完全可以忽略不计但是递归函数使用的运行时栈空间较大所以计算递归函数的空间复杂度时需要考虑运行时栈占用的空间大小。tips一般情况下leetcode递归函数的深度最大可以达到1e6这个量级左右。不同语言不同类型的递归函数波动较大该数据仅供参考。然后再回过来再思考这个算法的空间复杂度这个递归函数的调用树是一个二叉树的结构这里我们只计算空间复杂度的量级每个函数中的局部变量的空间复杂度为O(1)量级只需要考虑函数调用了多少次就可以了。