链式赋值

来自y老师模板的并查集(acwing 836)，路径压缩。

#include <cstdio>
using namespace std;
int a[10];
int c=20;
int df(int x){
    if(x<0) return c;
    else{
        a[x]=df(x-1);
    }
    return a[x];
}
int main(){
    df(3);
    for(int i=0;i<10;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    return 0;
}

题解：df(3)返回a[3];
a[3]=df(2)=a[2]=df(1)=a[1]=df(0)=a[0]=df(-1)=c=20;
这样最后a数组内值的状态：

20 20 20 20 20 20 0 0 0 0

选择返回值

如果数组q中有1，则输出“have 1” 否则输出“no 1”
1、调用递归可以有判断条件，这样可以利用条件提前终止递归，也是剪枝的一种操作。
2、本题用递归是练习如何处理递归的返回值，在计蒜客有一题“判断迷宫是否有通路“就用到了。

#include <cstdio>
using namespace std;
int q[10];
bool test(int q[]){
    for(int i=0;i<4;i++){
        if(q[i]) return true;
    }
    return false;
}
bool dg(int u){
    if(u>=4) return false;
    if(!q[u]){
        return dg(u+1);
    }
    return true;

}
int main(){
    for(int i=0;i<4;i++) scanf("%d",&q[i]);
    if(dg(0)) puts("have 1");
    else puts("no 1");
    return 0;
}

再次加深递归调用执行过程图

条件退出式的递归写法

博弈论的sg函数

int sg(int x){
    if(f[x]!=-1) return f[x];
    set<int> S;
    for(int i=0;i<m;i++){
        int t=s[i];
        //当x<t时，函数不再执行if语句，也就没有递归，执行后续语句，正常退出，并返回值。
        if(x>=t) S.insert(sg(x-t)); 
    }
    for(int i=0;;i++){
        if(!S.count(i)){
            return f[x]=i;
        }
    }
}