网传的一道2015阿里面试题：一台主流配置的PC上，调用f(35)所需时间，有两个版本：
++型
int f(int x)
{
int s = 0;
while (x++ > 0)
{
s += f(x);
}
return MAX(s, 1);
}
结果应该是stack overflow，只会执行
几毫秒
。
– -型
int f(int x)
{
int s = 0;
while (x-- > 0)
{
s += f(x);
}
return MAX(s, 1);
}
函数调用过程为
f
(
35
)
=
f
(
34
)
+
f
(
33
)
+
.
.
.
.
+
f
(
2
)
+
f
(
1
)
+
f
(
0
)
=
2
∗
(
f
(
33
)
+
f
(
32
)
+
.
.
.
+
f
(
2
)
+
f
(
1
)
+
f
(
0
)
)
…
=
2
34
f
(
0
)
\begin{aligned} f(35) &= f(34)+f(33)+….+f(2)+f(1) +f(0) \\ &= 2*(f(33)+f(32)+…+f(2)+f(1)+f(0))\\ &\dots \\ &=2^{34} f(0) \end{aligned}
f
(
3
5
)
=
f
(
3
4
)
+
f
(
3
3
)
+
.
.
.
.
+
f
(
2
)
+
f
(
1
)
+
f
(
0
)
=
2
∗
(
f
(
3
3
)
+
f
(
3
2
)
+
.
.
.
+
f
(
2
)
+
f
(
1
)
+
f
(
0
)
)
…
=
2
3
4
f
(
0
)
CPU主频为GHz量级，不妨取
C
P
I
f
(
0
)
=
5
CPI_{f(0)}=5
C
P
I
f
(
0
)
=
5
，总时间为
2
34
∗
5
÷
1
0
9
=
85.8993459
s
2^{34}*5 \div 10^9=85.8993459\ s
2
3
4
∗
5
÷
1
0
9
=
8
5
.
8
9
9
3
4
5
9
s
，所以结果是
几分钟
。实际跑出来的结果是88.903000。