数据结构：对于递归的理解和应用经验

数据结构：对于递归的理解和应用经验

目录

前言：

递归比较循环的优势：

1.递归和循环都是重复性质的操作，递归有清晰的层次：

2.循环结构回溯，中断继续操作较为困难：

3.总结（应用场景）：

如何去写递归代码：

1.对递归代码的理解：

2.广义表的创建：

3.广义表的输出：

总结：

来总结一下，首先是递归什么情况下好用：

递归到底是什么：

递归的核心思路：

---

前言：

        部分同学在写广义表的创建和输出时，在对递归代码的阅读，理解和写递归代码时有些许困难和迷茫。这篇博客主体是递归，循环会作为递归比较的客体，比较简略。

        首先会说明一些自己在递归上的理解，和相较于循环，递归的优势（不同于网上搜出来的优点缺点，那些东西讲的太简洁了，太抽象了，少了些废话，对于我们知识和见识不够深入的学生来说，有些难以体会和理解），我会主要根据自己写代码的经验讲实际的应用，最后我会完全从头到尾的演示我在写广义表的创建和输出的时候，思路和思考方式，过程演示，希望对同学们有帮助。

递归比较循环的优势：

1.递归和循环都是重复性质的操作，递归有清晰的层次：

        循环构建层次可以循环中嵌套循环，而对于层次数量不定的构建，很困难（我不会）。特别是在有分支层次的时候：比如树的遍历，图的遍历。我自己在用循环写分支有层次的时候很难进行下去。

2.循环结构回溯，中断继续操作较为困难：

        在具有分支层次的时候，递归可以调用自身中断当前操作，在递归结束后继续执行后续操作；而循环得通过嵌套，而countiue, break，跳过当前循环，和退出循环，都很难做到像递归一般，接着处理后续操作。

        例如在树的遍历当中，一个结点深度遍历到底了，需要回溯到上一个分支点继续深入，递归可以完美执行这一步操作，但是循环比较难实现。、

3.总结（应用场景）：

        循环很难对层次，分支层次进行操作，此时往往使用递归可以很好的解决。

如何去写递归代码：

1.对递归代码的理解：

        将某一堆重复的操作抽象出来，比如我们从小听的一个故事：

        从前有座山，山里有座庙，庙有老和尚和小和尚，老和尚给小和尚讲故事：从前有……；

        这个便是定义结构体一座山，定义一个结构体庙在山里，定义两个和尚在庙里，方法便是老和尚创建“山”这个结构体类型，并递归调用自身，传参山.庙.老和尚，无限递归。

typedef struct {    struct shan * old;        //老和尚struct shan * young;     //小和尚
}temple;        //庙typedef struct shan{temple *temple;     //庙
}mountain;        //山mountain * story(mountain *old) {//从前有座山（山开空间），山里有座庙 old = (mountain *)malloc(sizeof(mountain));//庙里有老和尚和小和尚（给庙temple开空间）	old->temple =  (temple *)malloc(sizeof(temple));//老和尚给小和尚讲故事：从前有座山（小和尚赋值为stroy，stroy传参为山里庙里老和尚） old->temple->young = story(old->temple->old); return old->temple->young; //无限递归 
} 

        总结下来便是：只操作一遍，只对第一遍操作负责，剩下的重复操作交给递归。对广义表来说，只用创建一个结点，孩子兄弟链的sublist指针，和link指针交给递归。

2.广义表的创建：

        先创建函数，确定好参数列表：纸上写好假设一个广义表g = (a,(b,(c)),d); 

typedef struct node {int tag;union{ElemType data;struct node *sublist;	}val;struct node *link;
}GLNode;GLNode *CreateGL(char *s, int *loca) {//大前提：字符串s是正确的广义表的括号表达式//loca用于指向字符串s中的字符
}

        画出广义表g的层次结构图（这次用孩子兄弟链结构）：

         我们要写递归代码，我们首先要明确中心思路，我们只对一个结点负责，我们只需要写好对于一个结点的创建，剩下的交给递归。

GLNode *CreateGL(char *s, int *loca) {GLNode *g;if(s[*loca] != '') {g = (GLNode *)malloc(sizeof(GLNode));}else return NULL;
}

        扫描字符串，如果到''说明广义表结束，返回NULL即可。如果不为''说明广义表未结束，需要创建结点：g指向一段新开空间。

GLNode *CreateGL(char *s, int *loca) {GLNode *g;if(s[*loca] != '') {g = (GLNode *)malloc(sizeof(GLNode));if(s[*loca] == '(') {}else if(s[*loca] == ')') {}else if(s[*loca] == ',') {}else {}}else return NULL;
}

        大前提是字符串是正确的广义表的括号表达式，所以可以列出可能读取到的字符串情况有4种：'(', ')', ',' , 原子。然后逐个分析：当读取到'(' 时意味着此时正在创建的是表结点，于是可以对表结点的tag，和sublist 进行简单的处理：

GLNode *CreateGL(char *s, int *loca) {GLNode *g;if(s[*loca] != '') {g = (GLNode *)malloc(sizeof(GLNode));if(s[*loca] == '(') {g->tag = 1;        //表结点tag = 1;(*loca)++;         //字符串向后读取一位;//子表交给递归处理g->val.sublist = CreateGL(s, loca);}else if(s[*loca] == ')') {}else if(s[*loca] == ',') {}else {}}else return NULL;
}

        记住我们只需要负责好我们当前结点的处理，不需要去管sublist递归怎么处理，操心好当下; 思考：如果我们处理好第一个元素了（不需要管是子表还是原子，都一样，放心交给递归处理）；继续分析：执行了if便会跳过else，处理玩第一个元素继续读取字符串，继续向后读取字符串，可能会读取到 ')' 或者 ',' 。

GLNode *CreateGL(char *s, int *loca) {GLNode *g;if(s[*loca] != '') {g = (GLNode *)malloc(sizeof(GLNode));if(s[*loca] == '(') {g->tag = 1;        //表结点tag = 1;(*loca)++;         //字符串向后读取一位;//子表交给递归处理g->val.sublist = CreateGL(s, loca);}else if(s[*loca] == ')') {}else if(s[*loca] == ',') {}else {}(*loca)++;//在大前提下，只有两种可能性：逗号或者反括号，列出if和elseif(s[*loca] == ',') {}else {}}else return NULL;
}

        继续分析：如果遇到逗号',' 说明正在处理的这个结点有“弟弟”结点，可以处理link指针指向弟弟结点：

GLNode *CreateGL(char *s, int *loca) {GLNode *g;if(s[*loca] != '') {g = (GLNode *)malloc(sizeof(GLNode));if(s[*loca] == '(') {g->tag = 1;        //表结点tag = 1;(*loca)++;         //字符串向后读取一位;//子表交给递归处理g->val.sublist = CreateGL(s, loca);}else if(s[*loca] == ')') {}else if(s[*loca] == ',') {}else {}(*loca)++;//在大前提下，只有两种可能性：逗号或者反括号，列出if和elseif(s[*loca] == ',') {(*loca)++;g->link = CreateGL(s, loca);}else {}}else return NULL;
}

        记住：我们只需要负责好我们正在处理的这个结点，剩下的不管是弟弟还是儿子都交给递归解决就好了。继续分析：如果我们遇到反括号，那说明：这个结点没有“弟弟”结点了，可以结束了，给link指针赋值为NULL就好,最后再返回g：

GLNode *CreateGL(char *s, int *loca) {GLNode *g;if(s[*loca] != '') {g = (GLNode *)malloc(sizeof(GLNode));if(s[*loca] == '(') {g->tag = 1;        //表结点tag = 1;(*loca)++;         //字符串向后读取一位;//子表交给递归处理g->val.sublist = CreateGL(s, loca);}else if(s[*loca] == ')') {}else if(s[*loca] == ',') {}else {}(*loca)++;//在大前提下，只有两种可能性：逗号或者反括号，列出if和elseif(s[*loca] == ',') {(*loca)++;g->link = CreateGL(s, loca);}else {g->link = NULL;}}else return NULL;return g;
}

        我们刚刚完整分析了如果先读取到前括号'(' 的情况时候的处理；我们还可能会读取到其他三种情况，根据刚刚的分析，我们如果读取到反括号或者逗号的情况已经再下面处理过了，下面有个指针后移(*loca)++; 所以我们只需要指针回溯一下，交给下面去处理即可：

GLNode *CreateGL(char *s, int *loca) {GLNode *g;if(s[*loca] != '') {g = (GLNode *)malloc(sizeof(GLNode));if(s[*loca] == '(') {g->tag = 1;        //表结点tag = 1;(*loca)++;         //字符串向后读取一位;//子表交给递归处理g->val.sublist = CreateGL(s, loca);}else if(s[*loca] == ')' || s[*loca] == ',') {(*loca)--;}else {}(*loca)++;//在大前提下，只有两种可能性：逗号或者反括号，列出if和elseif(s[*loca] == ',') {(*loca)++;g->link = CreateGL(s, loca);}else {g->link = NULL;}}else return NULL;return g;
}

        注意：因为c语法不允许传参时用&所以我用的指针，cpp可以直接取地址符，用指针一定要打括号，因为优先级的原因。继续分析：剩下读取到原子的情况，如果读取到原子的元素，便可以对tag赋0，并且sublist指针我们就不需要了，我们给与它公用一段空间的data赋值就行：

GLNode *CreateGL(char *s, int *loca) {GLNode *g;if(s[*loca] != '') {g = (GLNode *)malloc(sizeof(GLNode));if(s[*loca] == '(') {g->tag = 1;        //表结点tag = 1;(*loca)++;         //字符串向后读取一位;//子表交给递归处理g->val.sublist = CreateGL(s, loca);}else if(s[*loca] == ')' || s[*loca] == ',') {(*loca)--;}else {g->tag = 0;g->val.data = s[*loca];}(*loca)++;//在大前提下，只有两种可能性：逗号或者反括号，列出if和elseif(s[*loca] == ',') {(*loca)++;g->link = CreateGL(s, loca);}else {g->link = NULL;}}else return NULL;return g;
}

        注意：此时应该想到，如果是空表的，该怎么处理，读取不到原子元素呀。继续分析：空表是’()'，两个括号紧挨着，所以我们只要读取到后括号判断前一个括号是不是前括号就行了。因为我们负责的是当前结点，如果是空表，那意味着当前结点不该存在，应该是空表，于是返回空就行了：

GLNode *CreateGL(char *s, int *loca) {GLNode *g;if(s[*loca] != '') {g = (GLNode *)malloc(sizeof(GLNode));if(s[*loca] == '(') {//读取到前括号说明当前结点是表结点g->tag = 1;(*loca)++;g->val.sublist = CreateGL(s, loca);}else if(s[*loca] == ')' || s[*loca] == ',') {(*loca)--;}else {//读取到原子元素时g->tag = 0;g->val.data = s[*loca];}(*loca)++;if(s[*loca] == ',') {(*loca)++;g->link = CreateGL(s, loca);}else {//如果是空表直接返回空值if(s[(*loca)-1] == '(') {return NULL;}g->link = NULL;}}else return NULL;return g;
}

3.广义表的输出：

        广义表的创建就写完了。再复盘一下：写递归从头到尾的思路就是对当前对象负责，考虑到当前对象的所有可能性，涉及到其他对象或者层次的，直接交给递归，啥也不用多想，只需要处理好当前对象的每一个部分就好。接下来我再带大家写一个输出方法看看思路是否记住了：

void DisGL(GLNode *g) {//传参g指针指向一个广义表，记住只用对这个表负责就好其他别管if(g == NULL) return;else {}
}

        首先是这个指针不为空，为空直接返回没啥好说的。接着分析：这个结点可能是表结点，也可能是原子结点，我们只需要看tag值就好了，这里tag只有两个值，所以直接if，else就好了：

void DisGL(GLNode *g) {if(g == NULL) return;else {if(g->tag == 0) {}else {}}
}

        接着分析：如果是原子结点，直接输出当前元素便好，处理完了结点的两个元素，剩下link指针,如果link为空说明没有“弟弟”，输出反括号，不为空则说明还有弟弟，输出逗号，并且递归调用，“料理”一下“弟弟”：

void DisGL(GLNode *g) {if(g == NULL) return;else {if(g->tag == 0) {printf("%c", g->val.data);}else {}if(g->link != NULL) {printf(",");DisGL(g->link);}else printf(")");}
}

        记住：只用对当前结点负责，不管是弟弟结点，还是儿子结点都交给递归处理！！继续分析：我们处理完原子结点的情况，如果tag==1，说明是表结点，因为我们原子结点采用的是直接输出，所以表结点除了多了括号和原子元素没有任何区别，我们只需要在表结点两侧加一对括号，处理交给递归即可：

void DisGL(GLNode *g) {if(g == NULL) return;else {if(g->tag == 0) {printf("%c", g->val.data);}else {printf("(");DisGL(g->val.sublist);printf(")");}if(g->link != NULL) {printf(",");DisGL(g->link);}else printf(")");}
}

        注意：这时候发现有问题了，有两种输出反括号的方式，第一种是包裹子表，第二种是在没有“弟弟”后输出反括号，应该是哪种？遇到这样的问题，不要寡想，运行一下代码，拿着结论去做证明题！！！

         可以看到第二种在没有“弟弟”后输出反括号，最后会多一个反括号，为什么？大家可以自己拿着代码多实验几组数，然后思考一下，我会将答案放在评论区。

总结：

来总结一下，首先是递归什么情况下好用：

        1.进行的操作具有层次性或者分支层次的时候：如树，图的一系列操作。

        2.需要进行回溯的时候：除2取余，除到最后一个输出，回溯到上一个输出，一直到最开始。

        3.对象的定义本就是递归定义的：广义表中的元素可以是广义表，这本就很递归。

递归到底是什么：

        最简单的理解就是，递归就是你完成一个操作模板，剩下的重复操作的部分交给递归，举个例子：

        老板交给你一个项目，你不可能一个人全做了，太累，你写个模板出来交给主管，主管按照模板完善，交给下面的负责人，层次递交到最底层，然后再层层上交，下面的负责人汇总给主管，主管整理交给你，你再收尾交给老板。

递归的核心思路：

        你就是当代00后员工，给多少钱干多少事，绝不多做一分钱的：你就只用管好你负责的对象，剩下的交给递归，毕竟你帮别人完成项目，老板也不给加班费。所以不要多管闲事，做好当前负责的对象，考虑到所有情况，剩下交给递归。

        OVER！