前言

抽到一个简单题，记录它是因为它代表着递归与非递归的一个典型区别。
我先写了一个递归的算法，但是我总感觉有坑，题目写的0 <= n <= 37，于是我输入37去测试，果然超出时间限制。于是换了非递归的方法。
下面就简单区分一下递归与非递归解决一个问题的区别。

一、区别

递归优点
递归用来处理那些可以把大问题拆解成很多相同的小问题的情况。设置一个递归出口，只需一个递归体，就能解决大问题。典型的大问题拆解成很多相同的小问题就是二叉树。当现实问题能转换为很多相同小问题集成的大问题，就可以使用短小精悍的递归来解决。
——>所以递归小巧方便。
递归缺点
A)第一，每一次递归都是压栈，函数的所有状态都被压入到函数栈中直到一个个函数的return。
——>这样会耗内存。
B)第二，递归容易计算一些重复的过程，就如接下来的题目，三次递归相加，但是中间有很大一部分都是相同的计算。如T_m，m<n。这种T_m被计算了很多次。
——>重复计算，耗费时间。

三、源代码

给出递归和非递归的源代码，方便比较分析。这里的递归是不会通过测试的，因为我输37都超时了。

1、递归

class Solution {
    public int tribonacci(int n) {
        if(n==0)
        return 0;
        if(n==1 || n==2)
        return 1;
        return tribonacci(n-1)+tribonacci(n-2)+tribonacci(n-3)
    }
}

2、非递归

class Solution {
    public int tribonacci(int n) {
        if(n==0)
        return 0;
        if(n==1 || n==2)
        return 1;
        int t0 = 0,t1=1,t2=1,t=t0+t1+t2;
        for(int i = 3;i<n;i++)
        {
            t0 = t1;
            t1 = t2;
            t2 = t;
            t = t0+t1+t2;
        }
        return t0+t1+t2;
    }
}