C递归 我转晕了 求解

gaoxian159753

int f(int n)
{
        if(n == 1 || n == 2)
        {
                return 1;
        }
        return f(n-1)+f(n-2);
}

int main()
{
        int a = 0;
        a = f(6);
        printf("%d",a);
        return 0;
}


返回值是  8

Matt_Sun

return f(5)+f(4)
return f(4)+f(3)+f(3)+f(2)
return f(3)+f(2)+f(2)+f(1)+f(2)+f(1)+1
return f(2)+f(1)+1+1+1+1+1+1
return 8

zealstar

我也略晕……

先分析这个f()这个宏
表达式 return f(n-1) + f(n-2)是最关键的东西，仔细看：
当n=1时返回 1
当n=2时返回 1
当n=3时返回 f(2)+f(1)=2
当n=4时返回 f(3)+f(2)=2+1=3
当n=5时返回 f(4)+f(3)=3+2=5
当n=6时返回 f(5)+f(4)=5+3=8

这样明白了吗？所谓递归，一般来说，就是用前一次，或者前n次的结果来进行各种计算得出最近一次的结果。这里除了第1次和第2次特殊以外，其他数字都是n因为只有n=1或者n=2时返回1。

还是汉诺塔，所谓n个环的汉诺塔，你需要的只是把n-1个环当成一个环来看，就好了。
虽然我也很不明白各种递归，但是你只要实际代入数字，你大概就会明白了。