数据结构与算法（小议递归）-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构与算法（小议递归）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

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

一、递归是什么？

用一个简单的例子来看：

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