前言

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

一、递归是什么？

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、引用一下力扣书中的一句话——学习好递归的重要方法是：先模仿，再练习，所以现在不会也没关系，多多模仿，懂我意思吧！