c语言函数递归与迭代详解（含青蛙跳台阶问题详解）

前言

1.递归是什么? 递归是学习C语言函数绕不开的一个话题，那什么是递归呢? 递归其实是一种解决问题的方法，在C语言中，递归就是函数自己调用自己。 这里有一个极其简单的递归代码：

#include<stdio.h>
int main()
{
	printf("1\n");
	main();//在main函数中调用main函数
	return 0;
}

那么输出结果显而易见就是无数的1在控制台中被打印出来。 当然，这样的代码是错误的，如果调试起来，就会发现编译器会报错

最简单递归报错

这是因为上面的递归只是为了演示递归的基本形式，不是为了解决问题，代码最终会陷入死递归，导致栈溢出(Stackoverflow)。

1. 递归是什么

递归的思想

把一个大型复杂问题层层转化为一个与原问题相似，但规模较小的子问题来求解；直到子问题不能再被拆分，递归就结束了。所以递归的思考方式就是把大事化小的过程。 递归中的递就是递推的意思，归就是回归的意思，接下来慢慢来体会。

递归的限制条件

递归在书写的时候，有2个必要条件:

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

在下面的例子中，我们逐步体会这2个限制条件。

2. 两个例子

举例2：求n的阶乘

一个正整数的阶乘是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数n的阶乘写作n!。

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

分析：

显然

n!=n*(n-1)!

比如：

5!=5*4!
4!=4*3!

那么，实际上，这个思路就是递归的大事化小的思想。

经过分析，我们可以发现，当 n==0 时n!==1，而在其他时候我们就可以通过上面的公式进行迭代计算。（尽管说我们也可以指定n==1时n!==1,但这样会导致我们不能方便地计算出0!，因此我们要去较小值0）

阶乘

实现

我们可以实现Fact 函数：

int Fact(int n)
{
	if (n == 0)
		return 1;
	else
		return n * Fact(n - 1);//Fact(n-1)就是n-1的阶乘
}

当然，我们还可以写一个main函数对此进行测试：

#include<stdio.h>

int Fact(int n)
{
	if (n == 0)
		return 1;
	else
		return n * Fact(n - 1);//Fact(n-1)就是n-1的阶乘
}

int main()
{
	int a = 0;
	a = Fact(5);
	printf("%d ", a);
	return 0;
}

阶乘测试结果

进一步分析

如果你是第一次接触递归，那么你一定会

return n * Fact(n - 1);//Fact(n-1)就是n-1的阶乘

这行代码产生疑惑，为什么Fact(n-1)就是n-1的阶乘？明明代码并没有完成阶乘的计算，这实际上是递归代码书写时一个重要思想：在向下递归时，要坚信它能完成你需要的功能。 来看递归的实现过程图：

过程图

在代码执行过程中，首先向下递归，每一层递归都希望它所调用的递归代码能为它带来需要的结果 （n-1的阶乘），直到递归达到限制条件（n==0）,那么就可以开始回归，那么调用n为0的代码（即计算1的阶乘的代码）得到了它需要的结果，那么继续回归，n为2的代码也可以得到它期望的结果，那么就会不断地回归，直到回归完成。

除了这个以外，初学者可能还会对为何会产生递归产生疑惑： 为何会有这样的一个过程？实际上，我们可以通过一些常见的代码解释这个问题：

#include<stdio.h>
int ADD(int a, int b)
{
	return a + b;
}

int main()
{
	printf("%d ", ADD(1, 2));
	return 0;
}

这是一个简单地加法函数，在mian函数中，printf对ADD的返回值进行输出。 当代码执行到这个printf函数时，它不会直接进行输出，而是先进如ADD函数计算结果，并得到返回值，然后这个返回值再被printf调用进行输出。 那么递归在一定程度上也是同理，比如在n为1的则一步：

int Fact(int n)//这里n被传参1
{
	if (n == 0)
		return 1;
	else
		return n * Fact(n - 1);//Fact(n-1)就是n-1的阶乘
}

显然地1!=0，因此执行else语句中的代码体，尝试返回 1 * Fact(0) ，但这里又对函数进行了调用，和上面的 printf 相同，代码会先进入 Fact(0) 中计算结果，再把返回值带到这里，再进行 return ，也就是回归，这是最底层的一次回归，而更高级的递归也是这个原理，只不过要执行它们的回归，需要许多次的回归才能实现。

举例2：顺序打印一个整数的每一位

输入一个整数m，按照顺序打印整数的每一位。 比如:

输入:1234  输出:1 2 3 4 
输出:520   输入:5 2 0 

分析

首先就是第一个问题：我们该怎么得到这个整数的每一位？ 我们可以通过循环这个代码（当然还需要一些限制条件）

int tmp = n % 10；
n/=10;

得到这个整数的每一位，但这样我们得到的是逆序的，该怎么得到顺序的？ 当然是通过递归了！ 我们来设置一个 Print 函数来实现打印数字的每一位。

代码实现

在实现这个代码时需要铭记：在向下递归时，要坚信它能完成你需要的功能。

我们以打印 1234 举例讲解： 其实观察后可以发现：我们想打印出来 1 2 3 4，只需要先打印出123，再打印出4就可以了。 那么我们就可以实现代码了：

Print(int a)
{
	if (a >= 10)//这就是限制条件，当a<10时，a只有一位数，不需要再向下递归了
		Print(a / 10);
	printf("%d ", a % 10);
}

1234

3. 递归与迭代

递归是一种很好的编程技巧，但是和很多技巧一样，也是可能被误用的，就像举例1一样，看到推导的公式，很容易就被写成递归的形式：

阶乘

Fact函数是可以产生正确的结果，但是在递归函数调用的过程中涉及一些运行时的开销。 这里先以函数栈帧的角度进行分析：

在C语言中每一次函数调用，都需要为本次函数调用在内存的栈区，申请一块内存空间来保存函数调期间的各种局部
变量的值，这块空间被称为运行时堆，或者函数。函数不返回，函数对应的栈帧空间一直占用，所以如果函数调用
中存在递归调用的话，每一次递归函数调用都会开辟属于自己的栈帧间，直到函数递归不再继续，开始回归，才逐层
释放栈帧空间。所以如果采用函数递归的方式完成代码，递归层次太深，就会浪费太多的栈帧空间，也可能引起栈溢
出的问题。

当然看不懂也没关系，下面会有更加直接的方式证明这一开销的存在！

当然，在证明之前，我们不妨先来看看如何避免这一开销，在进行对比。 如果不想使用递归，就得想其他的办法，通常就是迭代的方式（通常就是循环的方式） 比如：计算n的阶乘，除了上面的思路，也是可以产生1~n的数字累计并乘在一起。

int Fact(int n)
{
	int num = 1;
	for (int i = 1; i < n; i++)
	{
		num *= i;
	}
}

上述代码是能够完成任务，并且效率是的方式更好的。 事实上，我们看到的许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更加清晰,但是这些问题的迭代实现往往比递归实现效率更高。 当然，当一个问题非常复杂，难以使用迭代的方式实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。

举例3：求第n个斐波那契数

我们也能举出更加极端的例子，就像计算第n个斐波那契数，是不适合使用递归求解的，但是斐波那契 数的问题通过是使用递归的形式描述的，如下：

斐波那契

或许你很容易写出这样的代码：

int Fib(int n)
{
	if (n <= 2)
		return 1;
	else
		return Fib(n - 1) + Fib(n - 1);
}

让我们对这个代码进行测试：

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d\n", ret);
	return 0;
}

当我们输入 50 时，你会发现电脑需要很长的时间才能输出结果，这是为什么？

Fib(50)

其实递归程序会不断的展开，在展开的过程中，我们很容易就能发现，在递归的过程中会有重复计 算，而且递归层次越深，冗余计算就会越多。我们可以进行测试：

int count = 0;
int Fib(int n)
{
	if (n <= 2)
		return 1;
	if (n == 3)
		count++;//统计n==3的计算被计算了多少次
	else
		return Fib(n - 1) + Fib(n - 1);
}

n=30

一个相当夸张的数字！ 因此我们可以明白，在斐波那契的计算上使用递归是非常不明智的，因为实在有太多的冗余计算了。 我们可以考虑利用迭代来解决这个问题。

int Fib(int n)
{
	if (n <= 2)
		return 1;
	int a =1, b = 1;
	while (n - 2)
	{
		int c = a + b;
		a = b;
		b = c;
		n--;
	}
	return b;
}

迭代的方式去实现这个代码，效率就要高出很多了。 有时候，递归虽好，但是也会引入一些问题，所以我们一定不要迷恋递归，适可而止就好！！！

4. 拓展问题：

青蛙跳台阶问题
汉诺塔问题

这两个都是很著名的需要用递归来解决的问题，这里我们解决一下青蛙跳台阶问题，当然你也可以了解一下汉诺塔问题。

青蛙跳台阶

题干：青蛙一次能跳1或2级台阶，问青蛙跳上n级台阶有几种跳法？

青蛙跳台阶1

那么对于这个问题，我们可以逆向来分析。 我们可以先计算青蛙想要跳上最后一级台阶（登顶）有多少种可能：

n

显然，有两种办法，从n-1跳一级上去，从n-2跳两级上去。 那么我们设置num函数计算这个问题，则有num(n)=num(n-1)+num(n-2); 而num(n-1)和num(n-2)也可以用这样的思路进行递归。

在递归分析出来后，我们不妨想一下，这个递归的限制条件是什么？

我们不妨来分析一下： 如果递归中遇到了 第2级，该是多少？第二级台阶既可以从0级跳上来，也可以从1级跳上来，所以是2。 如果遇到了第1级，该是多少？第一级台阶只能从地面跳上来，所以是1。 那么这两个就是限制条件了！ 那么我们就可以写出青蛙跳台阶问题的解决代码了。

int num(int n)
{
	if (n == 1)
		return 1;
	else if (n == 2)
		return 2;
	else
		return num(n - 1) + num(n - 2);
}

这样我们就可以得出结果了。 当然，相信你在前面的推导过程中也发现了，青蛙跳台阶问题的实质就是一个斐波那契数列，那么我们也可以尝试通过迭代的方法进行计算，但这里不在赘述。

感谢您的观看，如果喜欢的话不妨顺手点个赞，收藏，评论，关注！ 我会持续更新更多优质文章！！