首页 > 试题广场 >

试问计算x(x(8))时需要计算（）次x函数。

[单选题]

设有递归算法如下，

int x(int n)
{
 if(n<=3)
     return 1;
 else
     return x(n-2)+x(n-4)+1;
}

```
8
```
```
9
```
```
16
```
```
18
```

推荐

tianyunzqs

选D

x(8)=x(6)+x(4)+1 递归计算x(8)第一次调用

x(6)=x(4)+x(2)+1 递归计算x(6)第二次调用

x(4)= x(2)+x(0)+1 递归计算x(4)第三次调用

x(4)= x(2)+x(0)+1 递归计算x(4)第四次调用

之后再调用x()计算黑体部分的结果(5次，加上前面4次，一共9次)，最后x(8)返回值为9

接着计算x(9)

x(9)=x(7)+x(5)+1 递归计算x(9)第一次调用

x(7)=x(5)+x(3)+1 递归计算x(7)第二次调用

x(5)=x(3)+x(1)+1 递归计算x(5)第三次调用

x(5)=x(3)+x(1)+1 递归计算x(5)第四次调用

之后再调用x()计算黑体部分的结果(5次，加上前面4次，一共9次)，最后x(8)返回值为9

所以总共调用x()的次数是9+9=18

编辑于 2015-01-30 12:09:49 回复(2)

阿锋

8 6 4 4 2 2 0 2 0 共9次。后面9同理

发表于 2016-08-29 23:20:23 回复(0)

zhisheng_blog

选D： 18次

根据题意，易得x(3) = x(2) = x(1) = x(0) = 1

x(8) = x(6) +x(4) +1

= x(4) + x(2) +1 + x(2) + x(0) +1 + 1

= x(2) + x(0) +1 + 1 + 1 +1 + 1 +1 + 1

= 9

x(8) 这个就调用了9次函数x(int n)

同理可得x(9)也是调用了9次函数x(int n)

所以总共18次。

发表于 2016-07-27 09:08:49 回复(1)

Findway_

编辑于 2016-10-04 09:15:45 回复(2)

treverof

参考上一题一位牛友的做法。

6 4

4 2 2 0

2 0

一共九个节点，即调用9次，因为每一次都加1，所以结果返回9

7 5

5 3 3 1

3 1

一共9个节点，所以一共9+9=18次

发表于 2016-09-27 20:23:59 回复(0)

牛客-007

答案：B

先计算内部的x(8)，x(8)=x(6)+x(4)+1;这里调用了3次

x(6)=x(4)+x(2)+1;这里又调用了两次（x(6)上面已经算了，这里不再计入次数）

x(4)=x(2)+x(0)+1;两次

x(2)直接得到结果，不需要再调用。

由于递归不记录已经计算过的结果，所以表达式x(6)+x(4)+1中的x(4)需要重新计算，需要两次

3+2+2+2=9次

发表于 2015-01-12 14:46:09 回复(1)

云云云一飞冲天

发表于 2022-08-20 21:02:51 回复(0)

行动pie

使用递归树，计算节点数即可

发表于 2019-09-15 12:14:23 回复(0)

我努力了，剩下的由上天了

这道题和上道题的区别在于x(4)出现了两次，在x(4)还有2次递归，递归的方法还是比较喜欢上一位牛友的画图方式

编辑于 2019-05-08 19:21:18 回复(0)

justorez

纸上画个二叉树就很容易计算出结果~

发表于 2019-03-23 22:38:48 回复(0)

侯卿

不要忘了x(8),x(9)他们各自本身还有一次。

发表于 2018-03-12 18:52:44 回复(0)

冰＋

只要出现f(n)，就调用1次。

发表于 2017-09-22 13:36:53 回复(0)

曾经飞翔过

画一下树的结构，很容易就算出来了

发表于 2017-08-31 14:40:43 回复(0)

huixieqingchun

每计算一次，都要调用一次，不要数错了，

发表于 2016-05-12 12:30:30 回复(0)

程序猿的bug

每个函数分别调用到最底层的次数

发表于 2016-01-29 11:44:54 回复(0)

codersong

x(8)计算了9次求得x(8)=9,x(9)也计算了9次，总共18次

发表于 2015-10-10 15:32:40 回复(0)

当我唱起这首歌

刚刚运行了一下，应该是9次啊

发表于 2015-09-18 18:17:13 回复(2)

提交观点

问题信息

C++工程师搜狗 2015 递归

来自：搜狗2015 C++工...

上传者：小牧魔法袋

难度：

17条回答 474收藏 11124浏览

试问计算x(x(8))时需要计算（）次x函数。

问题信息

热门推荐

相关试题