递归是个什么东西呢,从字面意思来理解好像是先给再还回来,事实上它也就是这个意思,从函数的角度讲就是自己调用自己。
如果以前没有学习过递归,看到下面的这个程序,你可能不理解什么意思。
#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项的运算结果,你会发现消耗的时间比较长。
递归解决问题的思想还有很巧妙的。
2021年3月11日