使用遞歸來計算要打印的東西的數量

我學習遞歸，並且有一個例子，我解決了將*字符寫入一定次數的問題。使用遞歸來計算要打印的東西的數量

例如：如果您要通過數字3，則應打印2^3顆星，以便打印出8顆星。

我應該打印2^k次，其中k是一個通過的整數。該問題的答案是：

public String printStars(int k) { 
    if (k == 0) 
     return "*"; 
    else 
     return printStars(k - 1) + printStars(k - 1); 
}

我似乎無法理解的調用堆棧，以及如何解決這個問題，我認爲它的方式，當我在3通爲INT K，它會做N - 1 3次，直到遇到基本情況，並在此之前返回2個星號，並且由於需要3個級別來獲得深度，它將打印3×2星，因此它將打印6顆星。這很奇怪，因爲大多數其他遞歸很容易讓我感到困惑。

來源

2016-03-15 user6064023

我假定你的意思'k'代替'Ñ '（反之亦然）。 –

我認爲最簡單的方式，看看它是剛剛展開每個函數調用：

當k = 3的return語句評估爲printStars(2) + printStars(2)。

所以它會調用左邊第一個將評估對printStars(2)：

printStars(1) + printStars(1) + printStars(2)

我們再次展開左側一個第一：

printStars(0) + printStars(0) + printStars(1) + printStars(2)

printStars(0)終將評價爲"*"所以我們會有

"*" + "*" + printStars(1) + printStars(2) == "**" + printStars(1) + printStars(2)。

而且我們已經看到，printStars(1) == "**"所以我們有：

"****" + printStars(2)。而且我們已經知道printStars(2)將解決什麼問題。

來源

2016-03-15 02:20:30

謝謝，我一直在關注它，但忘記了原來的printStars（＃）Call需要添加到您所遞交的內容。所以我得到的答案是正確的答案 - 你從原來的電話中得到的答案。謝謝你這樣解釋 – user6064023

只要按照通過代碼：

應該清楚的是，在非基本情況：

printStars(k).length() == 2 * printStars(k - 1).length()

因爲在這種情況下，值由下式給出

return printStars(k - 1) + printStars(k - 1);

使用這個觀察，我們可以通過感應證明：

printStars(k).length() == 2^k

（其中^表示功率，而不是逐位XOR）

的確在基礎情況下printStars(0).length() == 2^0
假設printStars(k - 1).length() == 2^(k-1)，printStars(k).length() == 2 * printStars(k - 1).length() == 2^k

QED。

來源

2016-03-15 02:16:56

謝謝你的解釋，這非常有幫助！ – user6064023

我想它一定是k或n？

遞歸工作原理：它spanns樹：

到printStars每次調用導致一個*（2^0）或兩個*（2^1）。

如果調用printStars（4）：

遞歸級別4 IST = 0，因此返回本身兩個單獨的呼叫收縮，每個參數（3）！

遞歸級別3 ist！= 0因此它返回兩個獨立調用自身的收縮，每個調用都帶有參數（2）。

遞歸級別2 ist！= 0因此它返回兩個獨立調用的收縮，每個調用都帶有參數（1）。

遞歸級別1 ist！= 0，因此它返回兩個獨立調用的收縮，每個調用都帶有參數（0）。

遞歸級別0 ist == 0因此每次調用返回一個*。

返回遞歸級別1，我們收到兩個*並簽約並返回它們。

回到遞歸級別2，我們收到兩個**並簽訂並返回它們。

回到遞歸級別3，我們收到兩個****並簽約並返回它們。

回到遞歸級別4，我們收到兩個********並簽約並返回它們。

所以呼叫者接收 '***************' 2^4 = 16 *的

caller     | 
k=4   /  \   (just call yourself 2 times an return contraction of both calls) 
k=3  / \ / \  (just call yourself 2 times an return contraction of both calls) 
k=2  /\ /\ /\ /\  (just call yourself 2 times an return contraction of both calls) 
k=1  /\ /\ /\ /\ /\ /\ /\ /\  (just call yourself 2 times an return contraction of both calls) 
k=0  ** ** ** ** ** ** ** **  (just return 2^0 = 1 '*')

來源

2016-03-15 02:25:09 cmks

偉大的圖表，謝謝你的迴應，這使得過程非常清晰，謝謝你的時間！ – user6064023

使用遞歸來計算要打印的東西的數量

回答

相關問題