計數遞歸調用

Question

有一個數學公式來計算遞歸函數被調用的次數爲下無需檢查與我的編譯

多少次會時與呼叫 mystery2調用mystery2遞歸調用（1000）？

public void mystery2(int n) 
    { 
    if (n <= 1) 
    System.out.print(n); 
    else 
    { 
    mystery2(n/2);    
    System.out.print(", " + n); 
    } 
} 

1，3，7，15，31，62，125，250，500，1000 = 10倍

Answer 1

使用一個靜態變量，或全球

public void mystery2(int n) 
{ 
    static count = 0; 
    count++; 
    system.out.print("We have called this " + count + "times before..."); 
    if (n <= 1) 
    System.out.print(n); 
    else 
    { 
    mystery2(n/2);    
    System.out.print(", " + n); 
    } 

} 

Answer 2

外方法使一個變量像mysteryCnt = 0; （必須初始化爲0），然後在ELSE塊內將其遞增，方法爲mysteryCnt ++;這可能會奏效。

else{ 
    mystery2(n/2); 
    mysteryCnt ++; 
    System.out.println(", " + n); 
} 

強尼Z有正確的想法，但你不能初始化變量的方法內，否則將永遠不會增加過去1;他這樣做的方式，它會設置爲0，然後每次調用該方法時都會增加到1。從LOG2（N）

Answer 3

使用小區

ceil(log2(1000)) = ceil(9.966) = 10 

Answer 4

沒有 「公式」，但有用於解決復發的一般技術。在這裏，你有復發

N(x) = 1 + N(floor(x/2)) 

與基本情況

N(1) = 1 

的N(x)的定義是「次mystery2數量，如果初始參數是x稱爲」。

復發是通過像集成公式那樣學習的「技巧」來解決的，否則就像生成函數那樣花哨的數學來解決。有時候近似值是你能做的最好的。根據你的情況，如果我們廢除地板運營商（或假設x是2的冪），那麼很明顯，

N(x) = 1 + log_2(x) 

我們可以驗證這一點。如果x是1，我們有N(x) = 1 + 0 = 1。對於x = 2，我們有N(x) = 1 + 1 = 2等等......對於x = 1024，它是N(x) = 1 + 10 = 11。

隨着樓層操作員，確切的答案是更復雜的，取決於x的奇數因子的數量，但上面的公式總是接近。

Answer 5

另一種選擇是將計數傳遞給你的方法;

public void mystery2(int n) { 
    mystery2(n, 1); 
} 

public void mystery2(int n, int count) { 
    if (n <= 1) 
    System.out.print(n); 
    else 
    { 
    mystery2(n/2, count+1);    
    System.out.print(", " + n + ":count=" + count); 
    } 
} 

編輯：我想到了一個更好的方法來做到這一點。你可以像這樣去返回計數。

public static void mystery2(int n) { 
    System.out.print("\ncount = " + mystery2(n, 1)); 
} 

public static int mystery2(int n, int count) { 
    if (n <= 1) { 
     System.out.print(n); 
     return count; 
    } 

    System.out.print(n + ", "); 
    return mystery2(n/2, count + 1); 
}