C语言基础知识(10): 递归

Fawziya ·

更新时间:2024-09-21

· 732 次阅读

文章目录1 什么是递归2 举例说明递归2.1 例12.2 例22.3 例3——阶乘方式1——使用循环的方式方式2——使用递归的方式2.4 例4——1+2+3+....+100之和方式1——使用循环的方式方式2——使用递归的方式2.5 例5——汉诺塔3 递归必须满足三个条件4 循环和递归的比较5 递归的应用

注：转载请标明原文出处链接：https://xiongyiming.blog.csdn.net/article/details/105643504

1 什么是递归

一个函数在它的函数体内调用它自身称为递归调用，这种函数称为递归函数。
简单的来说：递归就是一个函数自己直接或间接调用自己。

常见可以使用递归的例子有：

1+2+3+4+…+100的和求阶乘汉诺塔 2 举例说明递归 2.1 例1

#pragma warning( disable : 4996)
#include
#include
#include
#include
#include
void f();
void g();
void k();
int main()
{
	f();
	system("pause");
	return 0;
}
void f()
{
	printf("FFFF\n");
	g();
	printf("1111\n");
}
void g()
{
	printf("GGGG\n");
	k();
	printf("2222\n");
}
void k()
{
	printf("KKKK\n");
	printf("3333\n");
}

运行结果

在这里插入图片描述

2.2 例2

#pragma warning( disable : 4996)
#include
#include
#include
#include
#include
void f(int n);
int main()
{
	f(7);
	system("pause");
	return 0;
}
void f(int n)
{
	if (n == 1)
		printf("我自己调用自己\n");
	else
	{
		printf("n=%d\n",n);
		f(n - 1);
	}
}

运行结果

在这里插入图片描述

2.3 例3——阶乘 方式1——使用循环的方式

#pragma warning( disable : 4996)
#include
#include
#include
#include
#include
int main()
{
	int val;
	int i, mult = 1, s;
	printf("请输入一个数字：");
	printf("val=");
	scanf("%d", &val);
	for (i = 1; i <= val; ++i)
		mult = mult * i;
	printf("%d的阶乘是：%d\n", val, mult);
	system("pause");
	return 0;
}

运行结果

在这里插入图片描述

方式2——使用递归的方式

#pragma warning( disable : 4996)
#include
#include
#include
#include
#include
long f(long n)
{
	if (1 == n)
		return 1;
	else
		return f(n - 1)*n;
}
int main()
{
	int val;
	printf("请输入一个数字：");
	printf("val=");
	scanf("%d", &val);
	printf("%d的阶乘是：%d\n", val,f(val));
	system("pause");
	return 0;
}

运行结果

在这里插入图片描述

2.4 例4——1+2+3+…+100之和 方式1——使用循环的方式

#pragma warning( disable : 4996)
#include
#include
#include
#include
#include
int main()
{
	int sum = 0;
	for (int i = 1; i <= 100; i++)
		sum = sum + i;
	printf("1+2+3+...+100 = %d\n", sum);
	system("pause");
	return 0;
}

运行结果

在这里插入图片描述

方式2——使用递归的方式

#pragma warning( disable : 4996)
#include
#include
#include
#include
#include
//假定n的值是大于或等于1的值
long sum(long n)
{
	if (1 == n)
		return 1;
	else
		return sum(n - 1) + n;
}
int main()
{
	printf("1+2+3+...+100 = %d\n", sum(100));
	system("pause");
	return 0;
}

运行结果

在这里插入图片描述

2.5 例5——汉诺塔

#pragma warning( disable : 4996)
#include
#include
#include
#include
#include
//汉诺塔
void hannuota(int n, char A, char B, char C)
{
	/*伪代码
	如果仅有一个盘子
		直接将A柱子上的盘子从A移到C
	否则
		先将A柱子上的n-1个盘子借助C移到B
		直接将A柱子上的盘子从A移到C
		最后将B柱子上的n-1个盘子借助A移到C
	*/
	if (1 == n)
	{
		printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n", n, A, C);
	}
	else
	{
		hannuota(n - 1, A, C, B);
		printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n", n, A, C);
		hannuota(n - 1, B, A, C);
	}
}
int main()
{
	char ch1 = 'A';
	char ch2 = 'B';
	char ch3 = 'C';
	int n;
	printf("请输入要移动盘子的个数 :");
	scanf("%d", &n);
	hannuota(n, 'A', 'B', 'C');
	system("pause");
	return 0;
}

运行结果

在这里插入图片描述