“我调我自己”：C语言递归的浪漫，只有程序员才懂的幽默

码途随笔

发布于 2026-01-12 19:53:53

540

一、函数递归

递归是一种解决问题的方法，，也是一种算法，其实就是函数自己调用自己例如：

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

但是上面是个死递归，最终会导致栈溢出（因为每一次函数调用都会向栈区申请空间，运行时堆栈）递归层次太深也可能导致栈溢出的情况

1.1 递归的思想

把一个大的问题拆分为小的问题，层层往下拆分，核心的思想是把大事化小思考方式：先递推，再回归

1.2 递归的限制条件

上述有一个死递归的情况，正是因为没有限制条件导致

递归存在限制条件，满足条件就不再递归了
每次递归越来越接近限制条件

二、深入递归

函数递归，肯定是要封装成一个函数，所以以下例题都以函数为准

2.1 求n的阶乘

满足递归的条件，递归的条件为n>0,并不是平白无故就开始就递归，停下来的条件是n=0,并且n逐渐变小靠近停下来的条件，满足n等于0就停止了，这道题很好的体现了大事化小的思想

#include<stdio.h>
int Fuc(int n)
{
	if (n == 0)
		return 1;
	else
		return n * Fuc(n - 1);

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

先递推（不计算），当算出一个结果时，再回归回去图解：

解决问题的方法：

递归
非递归（迭代），也就是循环

递归的特点：使用少量的代码，完成复杂的任务，不一定效率高效

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

分析思路：以4位数为例，把4位拆成3位加一位，层层往下，递归的限制条件为多位数（n>9），递推的停止条件为一位数，每次n/10为print的参数，逐渐向停止条件靠近

原始逻辑：

#include<stdio.h>
void Print(int n)
{
	if (n > 9)
	{
		Print(n / 10);
		printf("%d ", n % 10);
	}
	else
	{
		printf("%d ", n);//n可以写成n%10,后面可以简化
	}
}
int main()
{
	int n;
	scanf("%d", &n);
	Print(n);
	return 0;
}

) 根据上述图片可以简化：

#include<stdio.h>
void Print(int n)
{
	if (n > 9)
	{
		Print(n / 10);
	}
	printf("%d ", n % 10);
}
int main()
{
	int n;
	scanf("%d", &n);
	Print(n);
	return 0;
}

图解：注意：每一个函数都开辟了空间，保留了空间里原来的数据

如果把printf()放在前面就倒过来打印

三、迭代与递归的选择

以2.2为例，递归往往占用太多空间，消耗的时间也多一些

以2.1为例，迭代占用的空间少一些

#include<stdio.h>
int Fuc(int n)
{
	int i = 0;
	int ret = 1;
	for (i = 1; i <= n; i++)
	{
		ret *= i;
	}
	return ret;
}
int main()
{
	int n;
	scanf("%d", &n);
	int ret = Fuc(n);
	printf("%d", ret);
	return 0;
}

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

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

但是如果递归的不恰当书写，会导致些无法接受的后果，那我们还是应该放弃使用递归，使用迭代解决问题

3.1 斐波那契数列

先看递归的方法

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

但是效率并不高,比如计算第40位斐波那契数时，需要计算第三位斐波那契数3千多万次，耗时间，效率低

原因分析：n越小，重复计算会越多，里面会有大量的冗余的计算

重复这么多，为啥不会栈溢出

其实它的层次（深度）并不多，计算多

迭代方法分析思路：设置3个变量就行了，每次保证a和b为要求的值的前两位

注意：要考虑周全，把n等于1或2考虑进来，所以c等于1

#include<stdio.h>
int count = 0;
int Fuct(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n >= 3)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}
int main()
{
	int n;
	scanf("%d", &n);
	int ret = Fuct(n);
	printf("%d", ret);
	return 0;
}

3.2 汉罗塔问题

逻辑：每次把下面一个盘子分开，移动到C盘，上面n-1移到另一盘,剩下的一盘移动到终点，n-1个盘子再移到终点

用move()模拟盘子移动的过程，逻辑实现过程用Hanoi()函数实现

#include<stdio.h>
void Move(char a, char b)
{
	printf("%c->%c ", a, b);
}
//pos1——初始位置
//pos2——中间位置
//pos3——终点位置
void Hanoi(int n, char pos1, char pos2, char pos3)
{
	if (n == 1)
	{
		Move(pos1, pos3);
	}
	else
	{
		Hanoi(n - 1, pos1, pos3, pos2);
		Move(pos1, pos3);
		Hanoi(n - 1, pos2, pos1, pos3);
	}
}
int main()
{
	Hanoi(3, 'A', 'B', 'C');
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-10-21，如有侵权请联系 cloudcommunity@tencent.com 删除

函数