如何计算用于在递归调用堆栈上保存输入的空间

Question

假设我有一个函数

public void dfs(int[] a, int[] b, int count){
if(count == 0) return;
dfs(a, b, count-1);
return;
}

我想计算dfs的空间复杂度。调用堆栈的深度将是count。然后，在每个调用堆栈上，我需要存储a和b的副本。基于此推理，我倾向于得出空间复杂性为：O((a.length+b.length(*count(。然而，我认为当Java将对象传递给函数时，它只是将a、b地址的副本传递给给定的函数。因此，我认为每个调用堆栈不需要O(a.length+b.length(空间来保存输入。它只需要存储a和b的地址的空间，这两个地址应该是恒定的。这是正确的吗？

Answer 1

您的最后一句话是正确的。没有对输入数组进行复制，因此所需的唯一额外空间是堆栈深度的线性空间：O(计数(。