【C语言——函数递归总结】

一.函数递归的概念

递归其实就是解决问题的办法，在C语言中，递归就是函数自己调用自己。

递：递推的意思。归：回归的意思。

 递归的思想：

把一个大型的问题层层转换成与原问题相似，但规模较小的问题来求解，直到子问题不能被再拆分，递归就结束了。所以递归的思想就是大事化小的过程。

二.递归的限制条件

递归在书写的时候有两个必要的条件：

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

三.递归的举例

代码举例：求n的阶乘

题目：计算n的阶乘（不考虑溢出），n的阶乘就是1~n的数字积相乘。

 分析和代码实现：

我们可以由阶乘的计算公式n!=n*(n-1)!总结出它的递推公式：

那么我们就可以写出函数Fact(n)就是求n的阶乘，那么Fact（n-1)就是求n-1的阶乘，函数如下：

int Fact(int n)
{
	if (n == 0)
		return 1;
	else
		return n * Fact(n - 1);
}

测试：

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

运行结果（这里不考虑n太大的情况，n太大存在溢出）：

画图推演：

四.递归与迭代（循环）

递归是一种很好的编程技巧，和很多编程技巧一样，也是可能被误用的。

事实上，我们看到的许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更加清晰，但是这些问题的迭代实现，往往比递归实现效率更高。

当一个问题很复杂时，难以使用迭代的方式实现时，此时递归实现的简洁便可以补偿它所带来的运行时开销。

SUM：

1.如果说一个问题的使用递归去写的时候，写起来很简单，并且写出来没有明显的问题，就可以使用递归。

2.但是如果使用递归存在明显的问题，那就得想办法写成迭代（循环）的方式。

代码举例： 

求第n个斐波拉契数。

对于这问题我们是用递归的方式描述，用迭代的方式进行写代码。

#include <stdio.h>
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;
	scanf("%d", &n);
	int m=Fib(n);
	printf("%d", m);
}

PS：递归虽好，但请不要迷恋递归！

关注博主，优质内容不断更新！