一 什么是递归？

程序调用自身的编程技巧称为递归（ recursion）。
递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接
调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的主要思考方式在于：把大事化小

二 递归的两个必要条件。

（1）存在限制条件，当满足这个限制条件的时候，递归便不再继续。
（2）每次递归调用之后越来越接近这个限制条件。

***********很重要，没有其中任意一个都可能是死循环************

三 上俩个小题讲解原理。 练习1

接受一个整型值（无符号），按照顺序打印它的每一位。
例如：
输入：1234，输出 1 2 3 4

#define _CRT_SECURE_NO_WARNINGS 1
#include

void print(int n)
{
	if (n > 9)
	{
		print(n / 10);
	}
	printf("%d ", n % 10);
}
int main()
{
	
	int num = 1234;
	print(num);
	return 0;
}

我们按照函数递归思想大事化小来看。可以把按顺序打印1234进行拆分成类似的子问题

拆分 1..按顺序打印     print(1234)

         2. 按顺序打印     print(123 ) 加打印 4

          3.按顺序打印     print(12)    加打印 3  加打印  4

 

          4.按顺序打印      print(1)   加打印 2  加打印 3  加打印  4

为了更加清晰，方便理解，我们来画以下递归的调用图

 

最后看结果

 

这里我们重复下递归正确使用条件：

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

                      if（n>9）
（2）每次递归调用之后越来越接近这个限制条件。

                     n/10

*******俩个条件必须同时满足，不然就是死循环了。程序卡死，栈溢出错误。

练习2

编写函数不允许创建临时变量，求字符串的长度。
 

int Strlen(const char* str)
{
	if (*str == '')
		return 0;
	else return 1 + Strlen(str + 1);
}
int main()
{
	int len = 0;
	
	char num[20]= "asdfghj";
		len=Strlen(num);
		printf("%d ",len);
	return 0;
}

这里的函数实现便是使用了递归思想，大事化小。 

练习3

用递归来求n的阶乘。（不考虑溢出）
 

 思路还是分解为子问题

分解：比如就4！

4！分成=4*3！=4*3*2!=4*3*2*1!，   

一直递归，知道递归到1！在一直返回去求出4!

 (前面画过一次了，这里就不画图了，)

练习4

用递归求第n个。（不考虑溢出）
 

斐波那契数：前俩个默认为1，后面的数等于前俩个数之和，

比如：1  1  2   3   5   8   13   21  ..........等等

 

知道没有大于二的斐波那契数递归才开始返回，有许多重复的计算，由此可见这种方法求斐波那契数效率非常之低，求一个稍微大一点的斐波那契数就需要计算机算很久了。

比如假设求   斐波那契数50.

画图

 许多的重复计算，效率太低了，数字一大拖垮计算机。哈哈哈哈哈

四 函数递归的几个经典题目。

可以自己去看看哦。之后有时间可能会更新的。
（1） 汉诺塔问题
（2）青蛙跳台阶问题

五 总结
 

（1） 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。
（2）但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。
（3）当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。