【C语言】函数递归 (包你懂的)

埋头编程

发布于 2024-10-16 17:21:50

8500

代码可运行

文章被收录于专栏：C/C++C/C++

运行总次数：0

代码可运行

1. 前言

在我们了解清楚函数的知识点后，我们还得认识一下函数递归。学好函数递归，也是在为我们后期提高自己代码编程的能力奠定基础。

那么，现在是侦破时间！！！

2. 递归的定义

递归其实是解决问题的一种方法，等到大家后面在学习数据算法与结构的时候还会遇见它。递归说白了就是函数自己调用自己。

现在我们写一个史上最简单的C语言递归代码：

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

上述就是一个简单的递归程序，只是为了演示递归的基本形式，不做它用。而上述的这个代码最终会陷入死递归，导致栈溢出（Stack overflow）。

2.1 递归的思想

这个知识点十分重要，也是我们在使用递归时的基本思想和思路方向。

把一个大型复杂的问题拆解成一个与原问题相似，当规模较小的子问题来解决。直至子问题不能再被拆分了，递归就结束了。如果子问题能够被一直拆分，停不下来，就会出现开头我们讲的死递归，也就是栈溢出现象。

总的来说，递归的思考方式就是把大事化小的过程。（这句话请牢记）

递归可以拆成两个字“递”和“归”。其中递”就是递推的意思，“归”就是回归的意思。如果还没理解，不用担心，接下来我们一起慢慢体会。

2.2 递归的限制条件

不敢想象，当一个函数无穷无尽的递归下去，会对计算机的内存造成多大的心理创伤。为了保护我们内存宝宝这颗敏感易碎的心灵，我们得给函数递归加以限制，让它达到某种我们希望的程度时就停止下来，然后得到我们想要的结果。所以，函数的递归时必不可少的！

那我们该怎么写递归的限制条件呢？

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

递归存在限制条件，当满足这个限制条件时，函数递归就不再进行下去。
每次递归调用之后越来越接近这个限制条件。

在下面的例子中，我们来逐步感受这两句话的魅力所在。

3. 递归举例

3.1 举例1：求n的阶乘

题目：计算n的阶乘(不考虑有溢出)，n的阶乘就是1~n的数字累计相乘。

3.1.1 分析和代码实现

那这里就会有一个问题，这个阶乘到底能藏得了多久？仔细思考，阶乘无非就是从自然数开始算起，而0的阶乘我们规定是1。因此，这个阶乘最多只能藏到0这个数字。

下面，总结以上思路，我给大家列出了这么一个公式：

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

int Fact(int n)
{
	if(n == 0) //n==0就是函数递归的限制条件
	{
		return 1;
	}
	else
	{
		return n*Fact(n-1); //Fact(n-1)这个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\n",ret);
	return 0;
}

3.1.2 画图演示

相信看完这幅图后，你对递归是如何运作的理解有更深一层了。

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

真热打铁，接着来！！！

题目：输入一个整数，按照顺序打印整数的每一位

3.2.1 分析和代码实现

首先看到这道题目，我们就会先想该如何将整数的每一位先弄出来，之后再打印。其实把整数每一位都弄出来不难，思路如下：

如果n是一位数，n的每一位就是n自己 n是超过1位数的话，就得拆分每一位比如：现在n=1234,那么我们可以这么做：先1234%10，可以得到个位数上的4；接着再将1234/10的结果重新赋值给n，此时n的值就为123（1234/10这步操作就相当于把4给除掉了）。然后继续对123%10，得到3，再除10去掉3，以此类推。但是这里有个问题，这样做的话，我们打印出来的数字顺序是倒着的。

但是我们有了灵感，我们发现其实⼀个数字的最低位是最容易得到的，通过%10就能得到。

那么我们可以先写一个函数Print打印n的每一位，如下表示：

Print(n)
如果n是1234，那表示为
Print(1234) //打印1234的每一位

其中1234中的4就可以通过%10得到，那么
Print(1234)可以拆分为两步：
1.Print(1234/10) //打印123的每一位
2.printf(1234%10) //打印4
完成上述的步骤，那就完成了1234每一位的打印

那么Print(123)⼜可以拆分为Print(123/10) + printf(123%10)

以此类推，就有：

那么完成代码也就比较清楚：

void Print(int n)
{
 	if(n>9)
 	{
 		Print(n/10);
 	}
 	printf("%d ", n%10);
}
int main()
{
	int m = 0;
 	scanf("%d", &m);
 	Print(m);
 	return 0;
}

在这个解题的过程中，我们就是使⽤了⼤事化⼩的思路。

把Print(1234) 打印1234每⼀位，拆解为⾸先Print(123)打印123的每⼀位，再打印得到的4
把Print(123) 打印123每⼀位，拆解为⾸先Print(12)打印12的每⼀位，再打印得到的3
直到Print打印的是⼀位数，直接打印就⾏。

3.2.3 画图演示

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

什么是斐波那契数列？

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N）

3.3.1 分析和代码实现

不难发现，从第三个数开始，每个数都是前两个数的和

2 = 1+1 3 = 2+1 5 = 3+2 …

看到这里，我想你的DNA已经开始躁动了。这不就可以用递归实现。

代码实现：

#include<stdio.h>

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

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