algorithm - 递归代码的空间复杂度

Question

考虑以下 Java 方法：

   public static void f(int n) {
    if (n<=1) { 
       System.out.print(n) ; 
       return; 
   }else {
       f(n/2) ;
       System.out.print(n);
       f(n/2);
    }
 } // end of method

问题 3. 让 S(n) 表示 f(n) 的空间复杂度。以下哪项陈述是正确的？

• 答：S(n) = (2n)
• B: S(n) = (n)
• C: S(n) = (log n) <- 正确答案，有人知道为什么吗？
• D：以上都不是

Answer 1

每当函数以递归方式调用自身时，所有局部变量都保留在堆栈上，并将一组新的变量压入堆栈以进行新调用。这意味着您关心最多有多少调用，换句话说，递归的最大深度是多少。

很明显它是 log n，因为连续的参数是 n, n/2, n/4, ..., 1。有一个恒定数量的局部变量，即 1（堆栈上需要空间）因此整体空间复杂度为 O(log n)。