递归的优点

缩小了问题的规模

以递归树去理解递归的过程

1、由根节点向叶节点下降。
2、叶节点只执行退出代码。
3、由叶节点向根节点上升。

递归和循环的区别

一、循环是从前往后，递归是从后往前。
举一个例子，打印10进制数x的二进制表示，用除以2求余法，先得到的余数应该在最右边，后得到的依次往左排。如果用循环解决就要从最高位开始计算。用递归计算这样写：

void d2(int a){
    const int base=2;
    if(a==0) return;
    d2(a/base);
    printf("%d",a%base);
}

1、a不停的除以base，做到了规模不断缩小，直到0停止。
2、在a递归到0之前，是不会执行printf语句的。所以做到了从后往前。

二、循环只能处理简单的循环节，如果复杂版的循环都要用递归，比较方便。
比如： 堆模板

递归和生活

想象一下这样的场景：某件事A我做不到，因为做A时会遇到事件B，而B做不到。如果你碰到过类似的场景，可以继续思考一下，B相对于A的难度或规模有没有降低那么一点点，如果有，还可以思考是不是B事件还可以转移成C事件，来继续缩小规模，直到能做到为止。例如：在第9排坐着的你，想对第1排的同学传个话，但你只能和第8排的同学说话，平时的你会说这件事我做不到，因为我只能和第8排的说话，现在学习了递归之后，你就会说：“虽然我做不到和第1排同学说话，但我已经缩小了和第一排同学的距离，由9-1到8-1。这个事件可以继续传递下去，知道第1排结束，在回归我这里，这就是“递归”。

实例代码

卢卡斯定理

int lucas(LL a, LL b, int p)
{
    if (a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

讲解：为什么要递归？本来lucas公式：C(a,b)%p=C(a%p,b%p)*C(a/p,b/p),其中这部分：C(a/p,b/p,p) 但是，a太大，b太小，导致a/p仍然太大，进行乘法long long都会溢出。所以，对C(a/p,b/p,p)再次使用lucas定理，为的就是缩小问题的规模，避免乘法导致的long long溢出问题。

谢尔宾斯基三角形

       /\
      /__\
     /\  /\
    /__\/__\
   /\      /\
  /__\    /__\
 /\  /\  /\  /\
/__\/__\/__\/__\

#include <iostream>
using namespace std;
const int N=2e3;
char s[N][2*N];
void shape(int n,int x,int y){
    if(n==1){
        s[x][y+1]='/';
        s[x][y+2]='\\';
        s[x+1][y]='/';
        s[x+1][y+1]='_';
        s[x+1][y+2]='_';
        s[x+1][y+3]='\\';
        return;
    }
    int p=1<<(n-1);
    shape(n-1,x,y+p);
    shape(n-1,x+p,y);
    shape(n-1,x+p,y+(p<<1));
}
int main(){
    int n,p;
    cin>>n;
    p=1<<n;
    shape(n,0,0);
    for(int i=0;i<p;i++){
        for(int j=0;j<p<<1;j++){
            if(s[i][j]==0){
                cout<<' ';
            }
            else{
                cout<<s[i][j];
            }
        }
        cout<<endl;
    }
    return 0;
}

讲解：仔细观察，每个图形都是由3个小一级的图形组成的。这个图形就是：

   g(n-1)
g(n-1)g(n-1)

当n=1时，我们就该跳出了，n=1的图形叫做单位图形。
解题的主要逻辑仍然是用递归缩小问题的规模。
提示：图形的宽度是 $2^{n+1}$ ，高度是 $2^n$