函数递归

什么是递归？

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

//打印数字
#include
void print(unsigned int n)
{
	if (n > 9)
	{
		print(n / 10);
	}
	printf("%d ", n % 10);
}
int main()
{
	unsigned int num = 0;
	printf("请输入要打印的整数:");
	scanf_s("%u", &num);
	print(num);
	return 0;

递归的两个必要条件

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

递归与迭代

//递归方式
#include
int Fib(int n)
{
	if (n <= 2)
		return 1;
	else
		return Fib(n - 1) + Fib(n - 2);
}
int main()
{
	int n = 0;
	printf("请输入整数n:");
	scanf_s("%d", &n);
	int ret = Fib(n);
	printf("第%d个斐波那契数是%d", n,ret);
	return 0;
}

以上代码效率太低，重复大量的计算

//迭代方式
#include
int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}
int main()
{
	int n = 0;
	printf("请输入整数n:");
	scanf_s("%d", &n);
	int ret = Fib(n);
	printf("第%d个斐波那契数是%d", n,ret);
	return 0;
}