1

关于java中递归的两个小问题。

public int recursiveFunc(int n) {
    if (n==0)
        return(1);
    else
        return( recursiveFunc(n -1) + 1 );
}

如果调用 recursiveFunc(150)，答案应该是 151。有人可以向我解释一下它是如何得到这个答案的/它需要什么步骤？

假设 recursiveFunc2(17) 的以下函数再次相同，答案是什么以及如何？谢谢。

public int recursiveFunc2(int n) {
    if (n == 0)
        return(0);
    else
        return( recursiveFunc2(n/2)+1 );
}
4

2 回答 2

3

如果您更换：

return( recursiveFunc(n1) + 1 );

和：

return recursiveFunc(n - 1) + 1 ;

它按预期工作。

对于第二个功能，它更有趣一些。想想你可以将 17 除以 2 多少次，直到达到 0（递归停止条件）？这有点棘手，但分析步骤：

recursiveFunc2(17) = 
recursiveFunc2(8) + 1 = 
recursiveFunc2(4) + 1 + 1 = 
recursiveFunc2(2) + 1 + 1 + 1 = 
recursiveFunc2(1) + 1 + 1 + 1 + 1 = 
recursiveFunc2(0) + 1 + 1 + 1 + 1 + 1 = 
                0 + 1 + 1 + 1 + 1 + 1 = 5
于 2012-11-01T08:21:28.390 回答
1

在分析递归时，您必须检查基本情况以获得最终结果。在此设置中，基本情况是

if (n == 0)
    return(0);

所以你可以从那里逆向工程，然后建立入口案例。在您的示例中，入口是 when n = 150。

基本情况

recursiveFunc(0)叫做。基本情况被击中n == 0并1返回。

积聚

1返回到之前的调用

return recursiveFunc( n - 1 ) + 1;//note that n was 1 to produce a call of 0

因此，recursiveFunc( 1 - 1 )变为 1，那条线看起来更像

return 1 + 1;

继续

进一步支持这一点，下一个调用将是返回2的位置。现在，应该有一个明显的模式。即，那个

A0 = 1;
A1 = A0 + 1;
A2 = A1 + 1;
...
An = A(n-1) + 1;
...
An = n + 1;

所以这就是你如何得出 A150 = 151 的结论，或者更明确地说，recursiveFunc(150) == 151。

于 2012-11-01T08:33:23.103 回答