递归与递推是编程问题中重要的思想，如何更好的理解？看完这篇文章你可能会有收获。

递归

递归定义

递归，就是在运行的过程中不断调用自己本身。可以分为“递”和“归”两个过程，“递”得到每一个小步的结果，再通过“归”将每次运算的结果结合起来。最后得到答案。

递归优缺点

优点：代码简解易懂，思维方式符合我们思考的逻辑。
缺点：运行效率低，需要调用很多栈来储存返回点和局部量等，容易造成栈溢出。

递推

递推定义

递推，就是从问题的初始条件出发，通过观察得出某种关系式，通过这个关系式推出各项结果。

递推优缺点

优点：很好的发挥了计算机重复计算的优点，不会像递推一样占用过多的内存空间。
缺点：想象不到递推的关系式，从源头上直接gg（doge 。

例子

裴波那契数列

有一对小兔子，从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。按此规律，假设没有兔子死亡，第一个月有一对刚出生的小兔子，问第n个月有多少对兔子？

在草稿纸上进行简单的演算，我们会发现:第一个月1对，第二个月1对，第三个月2对，第四个月3对，第五个月5对，第六个月8对，第七个月13对……从第三项开始，每个月的数量都是前两个月的和

不难得出，当n>=3时，本月兔子数量=上个月数量+上上个月数量。

递归、递推代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int digui(int n)    //递归
{
    if(n==1||n==2)
        return 1;
    else
        return (digui(n-1)+digui(n-2));
}

int ditui(int n)    //递推
{
    int x=1,y=1,z;
    if(n==1||n==2)
        z=1;
    else {
        for(int i=0;i<n-2;i++){
        z=x+y;
        x=y;
        y=z;
        }
    }
    return z;
}

int main()
{
    int n;
    scanf("%d",&n);
    printf("%d\n",digui(n));
    printf("%d\n",ditui(n));
    return 0;
}