您现在的位置是:首页 >技术交流 >数据结构与算法(小议递归)网站首页技术交流

数据结构与算法(小议递归)

无证的攻城狮 2023-06-26 12:00:02
简介数据结构与算法(小议递归)


前言

递归是一种常用的算法设计,递归就是一种循环推理。简单来说就是调用原算法本身的算法。
这里主要探讨递归的使用,


一、递归是什么?

用一个简单的例子来看:

#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验算了一下,对的!


总结

从上面的例子可以看出:递归这算法至少在裴波那契数列计算时是不怎么适用的,更别提有些人所说的,把所有循环都用递归来写了!当然在递归深度不大时,还是可以用的。毕竟代码简洁!

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。