C语言：函数递归

#include<stdio.h>
int main()
{
	printf("haha\n");
	main();
	return 0;
}

先来看这段代码，这是最简易的一段递归的代码。当我们打印完haha后会main函数调用自己，这样就会使屏幕一直打印haha，但是会停止，这是为什么呢？因为当我们为main函数在栈区开出的内存被不断使用，最后导致栈溢出，最后程序就崩了。当然这是一段不正确的递归函数，这里只是先用它引出递归的思路。说白了，递归的本质就是函数自己调用自己。

#include<stdio.h>
int Fact(int n)
{
	if (n > 1)
	{
		return Fact(n - 1) * n;
	}
	else
		return 1;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d", Fact(n));
	return 0;
}

这是一段用递归思路写出来的算阶乘的代码，当n为1时，阶乘就等于1，当n大于1后，我们会发现

我们的Fact(n)函数所返回的值就等于Fact(n-1)*n，这时我们就可以使用递归使函数自己调用自己，最后算出阶乘。递归分成递推和回归。在这段代码中，当我们输入n为3时，Fact(3)函数返回时需要得到Fact(2)的值，再不断推到Fact(1)的值，这就是递归中的递推。当我们推出Fact(1)的值之后，我们就可以依次求出Fact(2),Fact(3)的值，这就是递归的回归。

如果我们使用递归函数，有两个要求需要满足。1.递归需要限制条件2.递归调用之后必须要变得更加接近限制条件。有了这两个条件才是正确的递归函数，否则会使函数不断递归，最后栈溢出。

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

这是一段打印整数每一位的代码，使用print函数来打印每一位的数，要从第一位开始。所以我们可以用n/10从n递推到第一位，然后一位位回归，回归时取得都是最后一位，所以用n%10。

综上所述，递归其实是一个很好的编程方式，但有时候也会有不足之处，例如用于斐波那契数列时，由于递归后很多数据都会重复计算，降低了计算的速率。不仅如此，在C语言中每一次函数调用，都需要为本次函数调用内存的栈区，申请一块内存空间来保存函数调用期间的各种局部变量的值，这块空间被称为运行时堆栈，或者函数栈帧。函数不返回，函数对应的栈帧空间就一直占用，所以如果函数调用中存在递归调用的话，每一次递归函数调用都会开辟属于自己的栈帧空间，直到函数递归不再继续，开始回归，才逐层释放栈帧空间。所以如果采用函数递归的方式完成代码，递归层次太深，就会浪费太多的栈帧空间，也可能引起栈溢出(stack overflow)的问题。