递归函数：可以简单的理解为函数自己调用自己（要用出口，让函数跳出递归，以免出现无限额递归即死循环）

                 递归由两部分构成：函数关系和出口

eg:

求1+2+3+4+5....+9的和？（利用递归函数）

分析；（1）函数关系f(n)=f(n-1)+n  (2) 出口：f(1)=1;

代码：

浅谈递归函数—C语言

递归函数的概念

1. 递归函数的定义：函数在其函数体内直接或间接调用它本身，则称该函数为递归函数。
2. 递归的两个必要条件：（1）存在限制条件，当满足这个限制条件的时候，递归便不再继续；（2）每次递归调用之后越来越接近这个限制条件。
3. 递归的主要思想：通过少量程序来描述解决问题过程所需的多次重复计算，即所谓的大事化小。
4. 拓展：每一次调用递归函数时，计算机都会为该函数重新分配新的内存空间，并且将原递归函数暂停（可以理解为开副本），然后现场保存一下，即利用堆栈保存暂定位置，以及参数值保存。

例题

编程离不开示例，我们现在以例题帮我们加深对递归函数理解。
1.计算n!（1×2×3×·······×n）
先来看看整个的代码:

#include<stdio.h>
int Fac(int n)
{
	if (n <= 1)//0！=1  1！=1
		return 1;
	else
		return n*Fac(n - 1);//递归函数，自己调用自己
}
int main()
{
	int n = 0;
	scanf("%d", &n);//存储用户输入的值
	int ret = Fac(n);
	printf("%d\n", ret);
	return 0;
}

我们以n=3为例子，来看看下面这张图的思路

要用递归我要先找到需要重复计算的部分：n*Fac(n - 1)，以及递归函数的出口n <= 1，有了这两个我们才可以设计程序。

拓展：每次调用递归函数，都会利用堆栈保存现场，以刚刚计算阶乘为例，其在堆栈保存如图所示，先入的放在最底下，这样返回的时候，程序就可以清晰的直到自己要去到什么位置，从什么位置继续执行程序，后面进入先出来，当然这是比较抽象理解，在计算机内部都是以二进制形式表示。

2. 计算斐波那契数
的确斐波那契数考虑到效率，较优解并不是以递归的形式，而是以迭代循环的形式计算，这里举例斐波那契数列只是为了了解递归。
首先理解什么是斐波那契数：

1 1 2 3 5 8 13 21 34......... 

从数学定义角度来看：
Fib(0)=1
F(1)=1
F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）
可以直观看出斐波那契数列在n>=2后其值为前两项之和
同样先看看代码：

int Fib(int n)
{
	if (n <= 2)
		return 1;
	else
		return Fib(n - 1) + Fib(n - 2);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d\n", ret);
	return 0;
}

我们以n=3为例子，来看看下面这张图的思路:

要用递归我要先找到需要重复计算的部分：Fib(n - 1) + Fib(n - 2)，以及递归函数的出口n <= 2，有了这两个我们才可以设计程序。

3.汉诺塔问题
汉诺塔游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置n个金盘，游戏目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

为了方便理解，用动态图来表示：（图片来源知乎）

用递归的思想，我们要找到递归设计的两个重要部分：（1）重复部分，即自相似部分；（2）递归的出口。
（1）重复部分：不难发现，圆盘移动分三步：
第一步 把n-1个圆盘从A杆经C杆移动到B杆；

第二步 将A杆上第n个圆盘移动到C杆；

第三步 然后再将n-1个圆盘从B杆经A杆移动到C杆。

同理移动n-1个圆盘与移动n个圆盘是相识的，但是又有细微的不同，就是圆盘的插入杆变化了。

所以我就先制定函数的参数：
int hanoi(int n, char A, char B, char C)

//hanoi 汉诺塔
//n表示圆盘数
//上式子可以表示为将n个圆盘从A经B移动到C

提取重复部分：
hanoi(n - 1, A, C, B)
//将n-1个圆盘从A经C移动到B

move(A, C);
//将第n个圆盘从A移动到C

hanoi(n - 1, B, A, C)
//将n-1个圆盘从B经A移动到C

(2)递归函数的出口：
但N=1 时 ，只剩下一个圆盘直接移动到C杆就可以
move(A, C)
//本质是打印：A=====> C

#include <stdio.h>
int count = 0;//计算移动次数
void move(char x, char y)
{
	printf("%c =====>  %c\n", x, y);
	count++;
}
int hanoi(int n, char A, char B, char C)// n表示圆盘个数，A,B,C为三个杆子，表示从A经由B移动到C
{
	if (n == 1)
		move(A, C);
	else
	{
		hanoi(n - 1, A, C, B);
		move(A, C);
		hanoi(n - 1, B, A, C);
	}
}
int main()
{
	int n;
	printf("请输入圆盘数：\n");
	scanf("%d", &n);
	count=hanoi(n,'A','B','C');
	printf("总共移动%d次",count);
	return 0;
}

总结

1. 递归程序设计的实质：把一个复杂的问题分解成若干子问题来处理时，其中某些子问题与原问题有相同的特征属性，则可以利用和原问题相同的分析处理方法(注意原问题与子问题能很好衔接)。
2. 在设计递归函数时候，要将每个递归函数看成简单的操作， 不要想得过于复杂。

函数递归

程序调用自身的编程技巧称为递归 recursion）

函数自己调用自己就是递归

你也可以理解成是一种嵌套结构，但递归分为俩部分，第一是“递”，进入嵌套结构。第二是”归“，最终会一步一步返回。第一次接触递归都会很懵，慢慢理解这个过程就明白了。

什么是递归？

递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接

调用自身的

一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，

递归策略

只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的主要思考方式在于：把大事化小

递归的俩个必要条件

代码引例1

接受一个整型值（无符号），按照顺序打印它的每一位。

例如：

输入：123，输出 1 2 3

参考代码：

#include <stdio.h>
void print(int n) {
 if(n>9)
 {
 print(n/10);
 }
 printf("%d ", n%10);
}
int main()
{
 int num = 123;
 print(num);
 return 0; }

运行结果如下：

我们要怎么理解这个函数递归的实现呢

我们可以采用画图方式理解这个过程

所以我们可以看到，递归必须满足俩个必要条件：

1.存在限制条件，当满足这个限制条件的时候，递归便不再继续。

2.每次递归调用之后越来越接近这个限制条件。

题中的限制条件就是（n>9),当我们的n通过（n/10)越来越少，直至n=1，无法满足时，递归停止，并开始返回。

这里有一个重要点就是print（n/10),如果没有这个条件，换成print（n）的话，n一直无法减小，一直进行递归。最后会导致栈溢出(Stack Overflow)。

栈溢出（Stack Overflow）

关于栈溢出，我就先简单介绍一下栈

栈：栈是一种计算机系统中的数据结构，它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来），是一种特殊的线性表。栈的操作常用的有进栈（PUSH），出栈（POP），还有常用的标识栈顶和栈底。

可以把栈想象成一摞扑克牌一样，一张一张叠加起来。

而栈溢出呢是缓冲区溢出的一种，缓冲区溢出：简单的说，缓冲区溢出就是超长的数据向小缓冲区复制，导致数据超出了小缓冲区，导致缓冲区其他的数据遭到破坏，这就是缓冲区溢出。而栈溢出是缓冲区溢出的一种，也是最常见的。只不过栈溢出发生在栈，堆溢出发生在堆，其实都是一样的。

而在代码引例1中

系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者（死递归），这样有可能导致一

直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出

合理使用递归

使用递归的宗旨是把大事化小

所以遇到问题时，我们应该明白是要把问题简单化，而不是习惯用递归，就一直用递归思考问题

我们应该清楚是不是用递归的思想会比较简单，或者换成递归的思想也可以实现，我们可以通过例题明白

代码引例3

求n的阶乘

用循环的方法，代码如下：

int main()
{
	int n = 0;
	int ret = 1;
	scanf("%d", &n);
	//循环产生1~n的数字
	int i = 0;
	for (i = 1; i <= n; i++)
	{
		ret = ret * i;
	}
	printf("ret = %d\n", ret);

	return 0;
}

而采用递归的话，代码如下：

int fac(int n)
{
	if (n <= 1)
		return 1;
	else
		return n * fac(n - 1);
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = fac(n);
	printf("%d\n", ret);
	return 0;
}

很多人刚学递归，都是懂了，但不知道怎么用。

而这道题可以先用公式来理解题目，再来用递归就容易多了

再来对比一下函数的代码，是不是清晰明了呢

代码引例4

求第n个斐波那契数。（不考虑溢出）

代码如下：

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

这道题同样我们也可以利用公式构造一个函数实现递归

具体思路如下：

解释要合理使用递归

通过以上俩个例题，我们可以发现俩个问题：

在使用 fib 这个函数的时候如果我们要计算第50个斐波那契数字的时候特别耗费时间。

使用 factorial 函数求10000的阶乘（不考虑结果的正确性），程序会崩溃。

为什么呢？

我们发现 fib 函数在调用的过程中很多计算其实在一直重复。

如果我们把代码修改一下：

int count = 0;//全局变量
int fib(int n) {
 if(n == 3)
 count++;
 if (n <= 2)         
 return 1;
    else
    return fib(n - 1) + fib(n - 2);

最后我们输出看看count，是一个很大很大的值。

那我们如何改进呢？

在调试 factorial 函数的时候，如果你的参数比较大，那就会报错： stack overflow（栈溢出）

这样的信息。

那如何解决上述的问题：

1. 将递归改写成非递归。

2. 使用static对象替代 nonstatic 局部对象。在递归函数设计中，可以使用 static 对象替代

nonstatic 局部对象（即栈对象），这不仅可以减少每次递归调用和返回时产生和释放 nonstatic 对象的开销，而且 static 对象还可以保存递归调用的中间状态，并且可为各个调用层所访问

比如，下面代码就采用了，非递归的方式来实现：

//求n的阶乘
int factorial(int n) {
        int result = 1;
        while (n > 1)
       {
             result *= n ;
             n -= 1;
       }
        return result; }
//求第n个斐波那契数
int fib(int n) {
     int result;
     int pre_result;
     int next_older_result;
     result = pre_result = 1;
     while (n > 2)
     {
           n -= 1;
           next_older_result = pre_result;
           pre_result = result;
           result = pre_result + next_older_result;
     }
     return result; 
     }

提示：

1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。

2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。

3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销

结束语

本人是学c小白，这些是近期学习整理总结，有什么不对欢迎大家指正，我会继续努力，谢谢~！