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

运行时栈

类c语言的函数调用原理都是如此，递归函数的空间复杂度是由递归的深度来决定的。

当程序运行时，运行时栈存储着程序的函数调用。每当有一个函数被调用时，就会有一个新的栈帧被压入栈顶，每当一个函数调用完成时，就会有一个栈帧弹出栈顶。每一个栈帧中存储函数调用的基本信息，其中包含函数参数和局部变量。

对于一般函数，运行时栈使用的空间与直接申请的空间相比较小，完全可以忽略不计，但是递归函数使用的运行时栈空间较大，所以计算递归函数的空间复杂度时需要考虑运行时栈占用的空间大小。

tips：一般情况下，leetcode递归函数的深度最大可以达到1e6这个量级左右。不同语言，不同类型的递归函数波动较大，该数据仅供参考。

然后再回过来再思考这个算法的空间复杂度，这个递归函数的调用树是一个二叉树的结构

这里我们只计算空间复杂度的量级，每个函数中的局部变量的空间复杂度为O(1)量级，只需要考虑函数调用了多少次就可以了。