首页 > 试题广场 >

设有一个递归算法如下，试问计算f(f(9))时需要计算（）次

[单选题]

设有一个递归算法如下

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

试问计算f(f(9))时需要计算（）次f函数。

```
10
```
```
11
```
```
12
```
```
14
```

查看答案及解析

赤默Windy

看备选答案数目不太多，就直接笔算了，不知还有没有更简便方法：

一、先算内层f(9)

[1] 计算 f(9) = f(7) + f(3) + 1;

[2] 计算[1]中 f(7) = f(5) + f(1) + 1;

[3] 计算[2]中 f(5) = f(3) + f(-1) + 1;

[4] 计算[3]中 f(3) = 1;

[5] 计算[3]中 f(-1) = 1;

{至此f(5)可计算得： f(5) = 1 + 1 + 1 = 3}

[6] 计算(1)中f(1) = 1;

{至此f(7)可计算得：f(7) = 3 + 1 + 1 = 5}

[7] 计算[1]中f(3) = 1;

{至此f(9)可计算得：f(9) = 5 + 1 + 1 = 7}

计算f(9)一共调用了7次函数

二、计算外层f(7)

由上面步骤可知，计算f(7)调用了5次函数

所以一共调用了函数7+5=12次

发表于 2017-08-18 21:07:06 回复(4)

呢称不能为空

因为else return后为两个函数相加并加1,所以可以用二叉树画图解决.

发表于 2019-06-08 22:23:39 回复(0)

華曲秦殇

发表于 2017-09-10 16:40:25 回复(2)

城枫墨凉

(1)内层： f(9)
|
return [f(7)+f(3)+1] = 5+1+1 = 7
|
return [f(5)+f(1)+1] = 3+1+1 = 5
|
return [f(3)+f(-1)+1] = 1+1+1 = 3

调用了f(9),f(7),f(3),f(5),f(1),f(3),f(-1),共7次。

(2)外层
因为f(9)=7 => f(f(9)) = f(7)
f(7)
|
return f(5)+f(1)+1 = 5
|
return f(3)+f(0)+1 = 3

调用了f(7),f(5),f(1),f(3),f(0),共5次。
加起来7+5=12次。答案C。

发表于 2018-01-11 10:21:26 回复(1)

蓝精灵与大鲨鱼

计算f(9)调用了7次，计算f(7)调用了5次，共调用12次。。

发表于 2018-01-04 21:03:09 回复(0)

牛客100902899号

有人和我一样是用口算的咩。。。

发表于 2020-03-13 06:27:04 回复(0)

拒绝了校花

f(9) 7次， f(7)5次画个递归树一目了然

发表于 2023-05-05 14:54:09 回复(0)

咕噜咕噜_Official

#include<iostream>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<cfloat>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

int counter = 0;

int f(int n) {
    counter++;
    if (n <= 3)
        return 1;
    else
        return f(n - 2) + f(n - 6) + 1;
}

int main() {
    f(f(9));
    cout << counter << endl;
    return 0;
}

输出为12。

编辑于 2020-04-26 00:43:48 回复(0)