【C语言篇】函数递归详解+汉诺塔问题、小青蛙跳台阶实例详解+浅谈递归优缺点_函数递归调用详解

1，递归定义

在一个函数体中，直接或间接的调用了这个函数本身。分为直接递归调用和间接递归调用

图解：1,直接递归调用：即函数体内部又调用了本身

void test()
{
	...
	test();
	...
}
int main()
{
	...
	test();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

这只是简单演示，test函数执行，在函数体内部又调用test(）函数，如此形成一个类似与循环的过程。（当然，这里肯定要有让“循环”停下来的条件，这也是下面会讲到的–递归出口）；

图解2：间接递归调用：

和直接递归调用不同，间接会设计到多个函数，如这里，add()函数执行的过程中会调用到test函数，而在test函数执行的过程中又调用add()函数，如此，也是一个“循环”的过程。

void add();//add的声明
void test()
{
	...
	add();
	...
}
void add()
{
	...
	test();
	....
}
int main()
{
	add();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2， 用递归解决求阶乘问题–详解

当然，在讲递归使用条件之前，我们用一个具体使用递归来解决问题的例子，去感受一下递归，从而更好的理解下面会总结的递归使用的条件和递归的注意事项。

问题：运用函数递归，求n 的阶乘

是不是看起来so easy！

#include<stdio.h>
int Fac(int n)
{
		return n * Fac(n - 1);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fac(n);
	printf("%d",ret);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

but…这样就行了吗？
no,no,no!!!
上面说到，递归其实类似与循环，那么我们联想一下循环，如果没有跳出循环的条件，循环是不会终止的。递归也一样，如果没有让递归停止下来的条件，也会是一个死递归。
再回过头来看这个代码，递归终止的条件是什么？或者说，递归终止的条件是什么？
是不是当n=1?Yes.你的n-1不可能无限进行下去，当n=1，也就是最简单的情况下（不需要由前面的小规模问题推导而来），是不是直接是return 1就好了。
那么我们来修改一下代码：

#include<stdio.h>
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",ret);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

我们用图解，来详细剖析一下这个递归进行的过程：

由上面这个例子，相信大家对递归应该有那么点感觉了吧
没关系，接下来我们看看对递归条件的具体描述，结合起来加深印象

3，递归调用的条件：