如何计算递归函数的空间复杂度

如何计算递归函数的空间复杂度

当使用递归实现heapify函数时，它将类似于以下伪代码：

heapify(arr, n, root):     largest = root     left = 2*root + 1     right = 2*root + 2    if left < n && arr[left] > arr[largest]: largest = left    if right < n && arr[right] > arr[largest]: largest = right     if largest != root:        swap(arr[root], arr[largest])        heapify(arr, n, largest)

回想一下，该

heapify

函数用于首先将数组变成堆，然后使用减小大小的堆对数组进行排序。

重要的是要注意，递归模式归结为尾递归。取决于语言功能，可以在不使用调用堆栈的情况下执行此 *** 作（调用循环会增加其使用空间）。

因此，除非递归算法也定义了 如何 在“幕后”实施递归调用（可能 不包括 尾递归机制），否则仍可以使用 O（1） 空间来实现。

但是，如果不使用尾部递归，则应考虑递归深度。该深度最多是（堆）树的深度，即 logn 。