推理遞歸函數

我正在通過羅伯特·塞奇威克和凱文·韋恩算法的第四版和我難倒鍛鍊1.1.27，詢問：推理遞歸函數

將用於遞歸調用的數量估算由代碼

public static double binomial(int N, int k, double p) 
{ 
    if ((N == 0) || (k < 0)) return 1.0; 
    return (1.0 - p)*binomial(N-1, k, p) + p*binomial(N-1, k-1, p); 
}

計算二項式（100,50）。

儘管我希望能夠幫助回答這個問題，但我也希望能更好地理解和推理這種性質的問題，所以我會讚賞任何幫助或指導。

來源

2013-05-26 Simon Morgan

'p'的初始值是什麼，假設爲'0'？ – lurker

你應該閱讀一些古老的數學家和科學家所做的。他們用來記錄他們手工完成的原始計算的頁面和頁面。有些人會寫出序列的前500名成員，以瞭解某些序列的屬性，其目標是幫助他們證明一些屬性。這同樣適用於...你是否嘗試插入一些值並手動寫出遞歸調用的數量？現在你可以稍微修改一下代碼，然後讓計算機告訴你;但在紙上做這件事並沒有什麼實際壞處 – rliu

@mbratch整個練習是在我的問題中，但我認爲它不重要，因爲它對函數的遞歸屬性 –

該算法遍歷Pascal三角形。

如果算法訪問每一個細胞一次，然後總是可以安排三角形遍歷爲矩形N * K. 100 * 50 = 5000。

下面是一個例子：

Pascal's Triangle with rectangle

在這個例子中N = 6和K = 4。

但是，問題是算法不記得它已經訪問過什麼單元，所以它冗餘地訪問單元。每次撥打電話的次數都會增加（哎呀，不好）。

如此這般1 + 2 + 4 + 8 + 16 + 32 + ...

2的冪的總和是2 ^（N + 1）-1，所以這將是2^101 - 1 = 2535301200456458802993406410751

這是一個很大的數字。不要運行這個程序。

（請注意，數字只是近似值，因爲如果K < 0有些呼叫不加倍，所以它可能會將上面的數字除以2）。

來源

2013-05-26 18:34:03

我認爲它比Pascal快得多，因爲有很多冗餘的遞歸調用。例如（3,2）會導致12個調用。 – rliu

這是真的，它不會被記憶，所以它冗餘地訪問單元格。 –

如果您從具體示例開始，您會立即看到該模式。對於N = 0，顯然它是0.對於N = 1，它是2次遞歸調用（因爲每個調用在直接劣等級上產生兩個遞歸調用，即對於N-1）

對於N = 2，那麼它是2 * 2 = 4

對於N = 3，那麼它的2 * 2 * 2（即2^3）

對於N = 4，那麼它的2^4

我假設你看到

來源

2013-05-26 18:33:37 mprivat

'k'小於'N'的情況如何？ –

（k <0）這種情況最先出現。所以2^50。 – Daedelus

推理遞歸函數

回答

相關問題