[面试题求解] 两道递归选择题求解
两道都是不定项选择题
10. The recursive function mystrlen(char *buf, int N)defined below tries to find the length of the first null-terminated string in the buffer buf(not counting the null character), where the buffer size is N. For instance if
buf = {'b','u','f','f','e','r','\0','a','b','c'}
with N = 10 is the input, the desired output is 6. If the buffer does not have any null character the desired output is N.
int mystrlen(char *buf, int N)
{
return mystrlen(buf, N/2) + mystrlen(buf + N/2, N/2);
}

What are all the possible mistakes in the code? （代码中可能的错误是哪个/些）
A. There are no mistakes in the code
B. There is no termination of recursion
C. The addition of the the two mystrlen()s in the recursion is incorrect
D. The use of N/2 in the recursion is incorrect
E. Recursion cannot be used to calculate this function

11. Continuing the above example, which of the following recursive implementations fix the code fully? （如果要修正以上的错误，应该）
A. No change to the code in example above
B.
int mystrlen(char *buf int N)
{
if(N==0)
return 0;
else
return mystrlen(buf, N/2) + mystrlen(buf + N/2, N/2);
}
C.
int mystrlen(char *buf int N)
{
if(N==0||buf[0]==0)
return 0;
else if (N==1)
return 1;
int t = mystrlen(buf, N/2);
if(t<N/2)
return t;
else
return (t + mystrlen(buf + N/2, (N+1)/2));
}
D. None of above

[解决办法]

引用:

为啥是0阿 有啥窍门否？

拆相即可
F(5N)=F(5N-4)+3(5N-5);
由于F(5)=5，所以F(5N)必然是5的倍数
[解决办法]
F(5N)=F(5N-4)+3(5N-5);应该是F(5N)=5×F(5N-4)+3×F(5N-5)
[解决办法]

引用:

F(5N)=F(5N-4)+3(5N-5);应该是F(5N)=5×F(5N-4)+3×F(5N-5)

应该是 F(5N)=5×F(5N-5)+3×F(5N-6)
[解决办法]

引用:

引用:F(5N)=F(5N-4)+3(5N-5);应该是F(5N)=5×F(5N-4)+3×F(5N-5)
应该是 F(5N)=5×F(5N-5)+3×F(5N-6)

不好意思。。是我笔误了
[解决办法]
看了下你们的回复,这样应该是好懂点吧
f(5n) = f(5n-1) + f(5n-2)
= f(5n-2) + 2f(5n-3) + f(5n-4)
= 5*f(5n-4) + 3*f(5(n-1));

3*f(5(n-1))除5取余的值与 f(5n)一致
以此类推，f(5n)%5 与 f(5) 一致，所以为0

[解决办法]

引用:

看了下你们的回复,这样应该是好懂点吧
f(5n) = f(5n-1) + f(5n-2)
= f(5n-2) + 2f(5n-3) + f(5n-4)
= 5*f(5n-4) + 3*f(5(n-1));

3*f(5(n-1))除5取余的值与 f(5n)一致
以此类推，f(5n)%5 与 f(5) 一致，所以为0

……

正解
[解决办法]
10 B 11 C 可对否
[解决办法]

引用:

1 BC
2 C

确实。。应该是BC
[解决办法]
“给定一个小点的输入，完整单步跟踪(同时按Alt+7键查看Call Stack里面从上到下列出的对应从里层到外层的函数调用历史)一遍。”是理解递归函数工作原理的不二法门！
递归函数关注以下几个因素
退出条件
参数有哪些
返回值是什么
局部变量有哪些
全局变量有哪些
何时输出
会不会导致堆栈溢出