C语言之函数递归讲解

苏小瀚

1295人浏览 · 2025-04-26 10:55:39

苏小瀚 · 2025-04-26 10:55:39 发布

1.什么是递归

递归是一种解决问题的方法，在C语言中递归就是函数自己调用自己，下面展示一个简单的递归的基本形式。

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

这里在进入main函数后，打印一次hehe，再次调用main函数继续打印hehe，这就是递归的基本形式，当然上述代码只是为了演示，代码最后会死循环，导致栈溢出。

什么是栈溢出？

我们都知道内存有栈区，堆区，静态区等空间，而每次函数调用都会向栈申请空间，上面代码重复调用main函数，不断的向栈申请空间，最终导致栈溢出。如左图我画的大概过程，仅供参考理解。

1.1 递归的思想

递归相当于把一个复杂的问题不断拆分成一个小的问题，直到拆分到最小的问题时，便停止递归，相当于把大事化小。递归也就是递推和回归的意思。

1.2 递归的限制条件

递归存在一个限制条件，当符合这个限制条件时，便停止递归。当一个问题不断递归时，会越来越接近这个限制条件。

2.递归例子

2.1 求n的阶乘

我们想要求n的阶乘要先求(n-1)的阶乘，求(n-1)的阶乘先求(n-2)的阶乘，以此类推直到求到 0的阶乘等于1。如左图所示。

这样我们就可以自定义一个求n的阶乘的函数fact()；

当n等于0时，0的阶乘等于1，而这个就是本次递归的限制条件，而n>0时，求n的阶乘要再次调用函数求n-1的阶乘，以此重复调用，最后求0的阶乘时候停止递推，开始回归，求1的阶乘，2的阶乘，最后求的n的阶乘。

思路如下图：

代码如下：

#include <stdio.h>
int fact(int n)
{
	if (n == 0)
	{
		return 1;
	}
	else
	{
		return n * fact(n - 1);
	}
}
int main()
{
	printf("请输入一个数:");
	int input = 0;
	scanf("%d", &input);
	int a = fact(input);
	printf("%d\n", a);
	return 0;
}

2.2 顺序打印一个整数的每一位

例如输入一个整数1234，打印出来时是 1 2 3 4。

如果n是一位数，那么打印出来就是它本身，如果n是多位数，那么该如何处理呢？

我们就可以这样想，如果要打印4的话，需要先打印1 2 3，要打印3的话，需要先打印 1 2 ，要打印 2 的话，需要先打印 1 。

那么我们就可以自定义一个函数Print(); ，来打印输入整数的每一位。

如左图所示，想要打印1234每一位，需要先打印123每一位再打印4，想要打印123每一位，需要先打印12每一位再打印3，想要打印12每一位，需要先打印1每一位再打印2，1的每一位是打印1，便是限制条件了。
代码实现:

#include <stdio.h>
void Print(int n)
{
	if (n / 10 == 0)
	{
		printf("%d ", n);
	}
	else
	{
		Print(n / 10);
		printf("%d ", n % 10);
	}
}
int main()
{
	printf("请输入一个整数：");
	int input = 0;
	scanf("%d", &input);
	Print(input);

	return 0;
}

3.递归与迭代

递归是一种很好的解决问题的方法，但是也存在一些不好的地方，比如说上面的求n的阶乘的代码，

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

上述代码虽说可以产生正确结果，但是在递归函数调用的过程中会涉及一些内存的开销。

在C语言中每次调用函数，都会向内存中的栈区申请一块空间，用来存放函数调用期间用到的参数，局部变量等的值，这块空间被称为运行时堆栈，或者函数栈帧。

只要函数不返回，函数对应的栈帧空间一直被占用，直到函数递归开始回归时，才逐步释放调用的栈帧空间，如果问题需要的递归层次太深，会浪费很多栈帧空间，甚至会发生栈溢出的问题。

因此我们就需要使用别的方法，那就是迭代（循环是迭代的一种）。

比如：求n的阶乘就可以用循环的方法解决：

#include <stdio.h>
int fact(int n)
{
	int count = 1;
	int i = 0;
	for (i = 1; i <= n; i++)
	{
		count *= i;
	}
	return count;
}
int main()
{
	printf("请输入一个数:");
	int input = 0;
	scanf("%d", &input);
	int a = fact(input);
	printf("%d\n", a);

	return 0;
}

4.求斐波那契数列

斐波那契数列就是一组数，前两个数为1，第三个数是前两个数的和，第四个数是第二个数加第三个数，以此类推，得到一组数列：

1 1 2 3 5 8 13 21 34 55 ........

当你想求第n个斐波那契数，该如何去求?

4.1 递归

我们肯定第一想法是用递归的方法去求，便写出了下面的代码：

//求斐波那契数列（递归）
#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 a = fib(n);
	printf("%d", a);
	return 0;
}

用递归的方法去求一些小的数算的还是很快的，但如果输入的数过大，就会算的很慢，输入50都要算几分钟，效率太低了。

这是为什么呢？

因为函数在不断递归的过程中，每次递推都有重复计算的数，越往后后面递归，重复计算的数越多，导致冗余计算量越来越多，因此导致计算缓慢，效率降低。

4.2 迭代

那我们可以用迭代的方法求解决这个问题。

代码如下：

#include <stdio.h>
int fib(int n)
{
	int a = 1;
	int b = 1;
	int i = 0;
	int sum = 0;
	for (i = 2; i < n; i++)
	{
		sum = a + b;
		a = b;
		b = sum;
	}
	return sum;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int a = fib(n);
	printf("%d", a);

	return 0;
}

用迭代的方法就不会出现冗余的情况，并且占用的内存空间也小。

总体来说，递归有利有弊，要根据问题去选择合适的方法。