您现在的位置是:首页 >技术交流 >数据结构与算法(小议递归)网站首页技术交流
数据结构与算法(小议递归)
简介数据结构与算法(小议递归)
前言
递归是一种常用的算法设计,递归就是一种循环推理。简单来说就是调用原算法本身的算法。
这里主要探讨递归的使用,
一、递归是什么?
用一个简单的例子来看:
#include <sstream>
#include <iostream>
using namespace std;
int recur(int n){
if(n==1 || n==2) return 1;
return recur(n-1) + recur(n-2);
}
int main(){
int n = 100;
int res = recur(n);
cout << "the fib NO is: " << res << endl;
}
这是一个很流行的裴波那契数列计算函数,很多编程书籍喜欢拿这个数列做例子。当然一般不会这么写~
这函数看上去很优雅,简洁明了。程序出口是n等于1或2,当n一直减到1或2时给出返回值,不然就一直调用自己。实际计算机运行时,会把过程中不是1或2的计算都挂起,一直等到1或2,才一步步计算出结果。
不用怀疑它能不能计算出正确结果,只要你有足够的内存,它是能工作的。仔细想想也就能理解递归了!
二、在什么时候适用递归
1.测试一下
测试一下,用数据说话:
为了对比,我再用python3写了一个正常计算的函数如下:
import time
def fib(n):
a, b = 1, 1
for i in range(3, n):
a, b = b, a+b
return a+b
s = time.process_time()
res = fib(100)
end = time.process_time()
r = end-s
print("the fib NO is: " + str(res))
print("用时:", r)
嗯!python3写起来也很优雅。这里的range(3, n)是为了和C++的计算结果得到同样的答案。
先测试第10位:
C++:用时1.188
python3:1.4000000000000123e-05
看到了吧,用这办法,C++远远跑不过python3,当然这有编译过程的问题,它并不能反应真实的情况,我们用更大的数据来测试。
再试试第100个裴波那契数
C++在我这十年前的8G内存电脑上算不出来了…等了60秒都没结果!还好MAC不怎么爱死机…还能接着写~
python呢?
老快了,也不知道这结果对不,怎么第100个就这么大了~
我又用C验算了一下,对的!
总结
从上面的例子可以看出:递归这算法至少在裴波那契数列计算时是不怎么适用的,更别提有些人所说的,把所有循环都用递归来写了!当然在递归深度不大时,还是可以用的。毕竟代码简洁!
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。