Question

超简单的一道数据结构题

int f(int n)
{
if(n<=2)
return 1;
return (2*f(n-1)+3*f(n-2));
}
求n=6的值
//1.f(6)=2*f(5)+3*f(4)
//f(5)=2*f(4)+3*f(3)
//f(4)=2*f(3)+3f(2)
//f(3)=2*f(2)+3*f(1)，这时求出了f(3)的值，是不是接下来求3*f(2)的值，
f(4)=2*f(3)+3*f(2)，这样求出f(4)后，是不是求3*f(3)...我想知道计算机内部
详细的递归顺序是怎么样?

Answer 1

求n=6的值
//f(6)=2*f(5)+3*f(4)
//f(5)=2*f(4)+3*f(3)
//f(4)=2*f(3)+3f(2)
//f(3)=2*f(2)+3*f(1)，求出了f(3)就把f(3)往前面的f(3)里带
f(4)=2*f(3)+3*f(2)，求出了f(4)后,f(5)=2*f(4)+3*f(3)就开始求后面的3*f(3)了

递归是用栈来协助完成的,你可以借助画数来帮助理解,
从顶层的f(6)=2*f(5)+3*f(4)
/ \
f(5)=2*f(4)+3*f(3) f(4)=2*f(3)+3f(2)
/ \ / \
.................................
(后面的依次下去,最后从低层往上递归计算)

计算机在计算f(6)时,要计算就把当前的信息压入栈,一直下去
也可以用栈来帮助理解递归

PS:希望对你有帮助~~呵呵~~

Answer 2

递归你就应该反过来算。。。，
n=1时，f（1）=1；
n=2时，f(2)=1；
f（3）=5；
f（4）=13；
f（5）=2*13+3*5=26+15=41；
f（6）=82+39=121；
没错的话是这样

Answer 3

在函数刚进入的时候下个断点，跟一下，看函数调用的先后顺序就知道了。你可以试一下，看n值的变化是不是这个顺序6，5，4，3，2，1，2，3，2，1，4，3，2，1，2