一道西山居的面試題，求好的解題思路？

---

首先cc函數肯定返回4，這個不用想都明白。

假設f(x)是調用cc(x)輸出的4的數量，那麼：

f(4) == 0
f(x) == (4-x) + f(x+1) + ... + f(4)
== (4-x) + sum(x+1 &<= y &<= 4, f(y)) 令g(x) == sum(x &<= y &<= 4, f(y)) /* 也就是 f(x) + f(x+1) + ... + f(4) */，有 f(x) == (4-x) + g(x+1) == g(x) - g(x+1) g(x) == 2*g(x+1) + (4-x)

這樣就得到了g的數列生成函數。我們知道g(4) == f(4) == 0。所以倒推下來就可以了：

g(4) == 0
g(3) == 1
g(2) == 4
g(1) == 11


根據定義有

f(1) == g(1) - g(2) == 7


所以一共就輸出7個。

當然了，這個題目的數據量是如此之小，面試的時候就應該直接畫顆調用樹暴力算出來，根本就花不了幾秒鐘，沒事不要去想什麼推導。

cc(1)
+-- "4" cc(2)
| +-- "4" cc(3)
| | +-- "4" cc(4)
| |
| +-- "4" cc(4)
|
+-- "4" cc(3)
| +-- "4" cc(4)
|
+-- "4" cc(4)


數數一共7個。

---

我來貢獻一個比輪子哥好看的調用樹&<(╯3╰)&>

&" dw="1508" dh="606" class="origin_image zh-lightbox-thumb lazy" w="1508" data-original="https://pic2.zhimg.com/4f9706d2ccb893bde0646e9eb167e4dc_r.jpg" data-actualsrc="//i1.wp.com/pic2.zhimg.com/50/4f9706d2ccb893bde0646e9eb167e4dc_hd.jpg">

每條線都是一個遞歸路徑，都是遞歸到cc(4)時開始回溯

cc(4) = 4

cc(3) = cc(4) = 4

cc(2) = cc(3) = cc(4) = 4

cc(1) = 4（然而我們並不輸出cc(1)的返回值）

數一數一共7個cout

所以是7個4咯~

就醬~

--------------------------------------

另外，循環嵌套遞歸沒什麼難理解的，如果題主沒學過DFS，去看一看肯定有用

---

推薦閱讀：