C语言算法进阶——递归

学习算法的过程中，总会遇到一个让你耳目一新，惊为天算的方法——递归

1、递归的定义非常简单：函数直接或间接的调用自己；
2、但是在这短短几个字中，也蕴含着递归的思想：分而治之；
3、分而治之又是什么呢？其实也很简单，就是：将一个大问题分成多个小问题来解决；
4、递归分为两个过程，我个人喜欢称这两个过程为递和归；
5、递的过程就是分解大问题的过程，归的过程是整合小问题的过程，整体就像是栈，递是向栈中存数据，归是向栈中取数据。
说了这么多，递归到底是解决什么样的问题呢？

1.解决一些数学问题

（1）斐波那契数列
题目：斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
求n阶斐波那契数列。

int fib(int n) {     if(n==0)         return 0;     if(n==1)         return 1;     if(n==2)         return 1;     return fib(n-1)+fib(n-2); } 

（2）小青蛙跳台阶
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法？

int numWays(int n) {     if(n<1)         return 0;     if(n==1)         return 1;     if(n==2)         return 2;     return numWays(n-1)+numWays(n-2); } 

2.简化链表中一些操作

（1）清空链表

void free_list(Node *head) { 	if(head==NULL) 		return ; 	head=head->next; 	free_list(head); 	free(head); } 

（2）移除链表元素

struct ListNode* removeElements(struct ListNode* head, int val) {     if(head==NULL)         return head;     head->next=removeElements(head->next,val);     return head->val==val?head->next:head;  } 

3.解决树的绝大多数问题

（1）树的反转

void reverse_tree(Tree_Node *root) { 	if (root != NULL)     { 		Tree_Node *s;         s = root->left;         root->left = root->right;         root->right = s;         reverse_tree(root->left);         reverse_tree(root->right);     } } 

（2）树的遍历

void pre_traverse(Tree_Node *root) { 	if(root==NULL) 		return; 	printf("%-5d",root->data); 	pre_traverse(root->left); 	pre_traverse(root->right); } 

3.使用递归技巧

1、递归对解决链式结构问题有着天然优势，解决单链表通常只需要调用自己一次，解决二叉树通常要调用自己两次；
2、递归解决问题也分为两种方式，一个是在递的过程中解决问题，另一个是在归的过程中解决问题，比较经典的就是快速排序和归并排序(我之后会更新)。

1、递归在使用中是非常灵活的，也是非常难去想的，往往一个小问题都会在大脑中一遍一遍的绕，直到大脑爆栈。
2、作为一个小白来说，写这篇进阶确实不太好驾驭，还需要通过做题去熟悉，去磨练自己，第一篇文章的每日一练其实本意是挺好的，但是之后的题我没有去发，看看之后补发一下。
3、引用一下力扣书中的一句话——学习好递归的重要方法是：先模仿，再练习，所以现在不会也没关系，多多模仿，懂我意思吧！