递归是个什么东西呢，从字面意思来理解好像是先给再还回来，事实上它也就是这个意思，从函数的角度讲就是自己调用自己。
如果以前没有学习过递归，看到下面的这个程序，你可能不理解什么意思。
|
#include void wstring(int { if(n==0) { printf(“我是第%d次调用了\n”,n); return; } else { printf(“我是第%d次调用了\n”, n); wstring(n-1); } } int main() { wstring(10); return 0; } |
再改动一点细节，不知道是否好理解一些了。
|
#include void wstring(int { if(n==0) { printf(“我是第%d次调用了\n”,n); return; } else { printf(“我是第%d次调用了\n”, n); n = n – 1; wstring(n); } } int main() { wstring(10); return 0; } |
这个程序确实不好理解，如果换成这样是不是很明确了。
|
#include void wstring(int { for(int i=n;i>=0;–i) { printf(“我是第%d次调用了\n”, i); } } int main() { wstring(10); return 0; } |
上述的例子就是递归，常用给出的例子是斐波那契数列，1，1，2，3，5，8，……，这个数列的通项公式即an=an-1+an-2，n>=3，如果用递归的写法，示例如下
|
#include int Febo(int { if(n==1 || n==2) { return 1; } else { return Febo(n – 1) + Febo(n-2); } } int main() { int m = 12; printf(“第%d项为：%d\n”, m,Febo(m)); return 0; } |
我们再用循环写一次
|
#include int Febo(int { if (n == 1 || n == 2) { return 1; } else { int an1 = 1, an2 = 1, an3; for(int i=3;i<=n;++i) { an3 = an1 + an2; an1 = an2; an2 = an3; } return an3; } } int main() { int m = 12; printf(“第%d项为：%d\n”, m,Febo(m)); return 0; } |
我看到相关的参考资料上说，递归和循环是可以相互转换的，我也不太确定是不是所有的情况都可以。
递归运算牵扯到压栈出栈操作，不仅花费的时间多而且占用的空间也多，容易造成溢出，你可以试一下用上面递归的方法求第100项的运算结果，你会发现消耗的时间比较长。
递归解决问题的思想还是很巧妙的。