递归的学习与应用-创新互联

文章目录

前言
一、递归的定义
二、递归的演示
三、递归的基本原理
- 特点1
- 特点2
- 特点3
- 特点4
- 特点5
四、尾递归
- 例题1
- - 思考
- 例题2
- - 思考
- 例题3
五、递归的优缺点
- 优点
- 缺点
总结

创新互联公司一直秉承“诚信做人，踏实做事”的原则，不欺瞒客户，是我们最起码的底线！以服务为基础，以质量求生存，以技术求发展，成交一个客户多一个朋友！为您提供成都网站建设、网站设计、成都网页设计、小程序制作、成都网站开发、成都网站制作、成都软件开发、手机APP定制开发是成都本地专业的网站建设和网站设计公司，等你一起来见证！

前言

笔者本周粗略学习了递归，现以一下博客记录自习学习的过程，如果错误，请不吝指出。

一、递归的定义

c允许函数调用他自己，这种调用过程称为递归。递归有时难以捉摸，有时却很方便使用。结束递归是递归的难点.，因为如果递归代码中没有终止递归的条件测试部分，一个调用自己的函数会无限递归

二、递归的演示

# includevoid digui(int);

int main()
{digui(1);
	return 0;
}

void digui(int n)
{printf("%d  ,  %p\n", n, &n);//#1语句
	if(n<4)
	digui(n+1);
	printf("%d  ,  %p\n", n, &n);//#2语句
}

输出结果
1  ,  000000000062FE00
2  ,  000000000062FDD0
3  ,  000000000062FDA0
4  ,  000000000062FD70
4  ,  000000000062FD70
3  ,  000000000062FDA0
2  ,  000000000062FDD0
1  ,  000000000062FE00

我们通过以上程序分析递归的运行方式。
首先，main函数调用了带参数1的digui（）函数，所以第一步先执行带参数1的递归函数中的#1语句，当程序继续向下执行时，遇到了我们的递归函数，此时的递归函数中的参数是n+1，也就是2，那么重新开始一次新的digui（）函数，只不过此时的参数是2，然后继续打印参数为2的#1语句。

当递归函数调用到参数为4时，我们的digui（）函数便再调用自己，那么便打印#2语句。接着将控制权返回上一层digui（）函数，也就是digui（3）
因为digui（3）在刚开始并未执行#2语句，而是先被自己调用进入了新的函数，当递归结束时他的执行步骤的位置将会返回digui（3）后的下一步，也就是执行#2语句。

因此我们可以得出一条简单的函数调用链：digui(1)->digui(2)->digui(3)->digui(4)，当digui(4)结束后，将控制权返回digui(3)，那么有digui(4)->digui(3)->digui(2)->digui(1)

三、递归的基本原理

因为笔者的总结能力浅薄，所以也许看到上述文字你并不能很理解
接下来笔者将会给出递归的几个原理帮助你的理解、

特点1

每级函数都有自己的变量，也就是说，第一次函数调用的digui（n+1）与第二次函数调用的digui（n+1）不同，最终当程序返回digui（）的第一级调用时，最初的n仍是他的初值1

特点2

每次函数调用都会返回一次，当函数执行完毕后，控制权将会被传回上一级递归。程序必须按顺序逐级返回递归，不能跳级。

特点3

递归函数中位于递归调用之前的语句，也就是我们上面的#1语句，均按照被调函数的顺序执行。

特点4

递归函数中位于递归调用之后的语句，也就是我们上面的#2语句，均按照被调函数相反的顺序执行。

特点5

递归函数必须包含能让递归调用停止的语句。
通常，递归函数用if或其他等价的测试条件等于某特定的值时停止调用。
笔者将会在下文给出例题以解释。

四、尾递归

最简单的递归形式就是把递归调用放置于函数的末尾，即正好在return的语句之前
尾递归时最简单但的递归形式，因为他相当于循环。
我们以几道例题深入了解递归

例题1

以下是使用递归计算阶乘的代码

# includeint jiecheng (int n)
{int ans;
	if(n>0)//通常用if语句进行终止
	ans = jiecheng(n-1)*n;
	else
	ans = 1;//最需要我们注意的时递归的终止条件
	return ans;
}

int main()
{int i;
	scanf("%d", &i);
	printf("%d", jiecheng(i));
	return 0;
}

思考

可以使用循环与递归计算阶乘，那么使用哪一个好？
一般，选择循环比较好，首先，每次递归都会创建一组变量，所以递归使用的内存更多，而且每次递归都会把创建的一组新变量放在栈中，递归调用的数量受限于内存空间

例题2

以下是用递归将十进制转换为二进制
当函数执行完毕，从最后一层递归函数开始putchar二进制数，最后一层函数的putchar是二进制数的第一位
若不知道为何从最后一步开始返回，可以思考上方的特点4

# includevoid digui(int n)
{int r;
	r = n % 2;//十进制的第一次取模是二进制的最后一位 
	if (n >= 2)

		digui(n / 2);//每次使n变化 
	putchar(r == 0 ? '0' : '1');
	return;
}

int main()
{int n;
	while (scanf_s("%d", &n)==1)//scanf返回值为如果成功，该函数返回成功匹配和赋值的个数。如果到达文件末尾或发生读错误，则返回 EOF。
	{digui(n);
		printf("输入q终止");
		putchar('\n');
	}


	return 0;
}

思考

一般而言，对于数字n，其二进制的最后一位是n%2，因此，计算的第一位数字正好是待输出二进制的最后一位，这一规律提醒我们，在递归函数之前计算n%2，在递归之后打印计算结果。且要获得下一位数字，必须把原数除2，这种计算方法相当于在十进制下把小数点左移一位。且通过putchar(r == 0 ? ‘0’ : ‘1’);将数值转换成字符

例题3

以下是用递归合并两个有序链表
合并两个有序链表

# include# includetypedef struct Node
{int data;
	struct Node* pNext;
}NODE, *PNODE;

PNODE CreateList()
{PNODE pHead = (PNODE)malloc(sizeof(NODE));//链表不用预先设定长度
	PNODE pTail = pHead;
	int val;
	int len;
	printf("请输入链表的长度");
	scanf_s("%d", &len);
	for (int i = 0; i< len; ++i)
	{PNODE pNew = (PNODE)malloc(sizeof(NODE));
		printf("请输入第%d个节点的值", i + 1);
		scanf_s("%d", &val);
		pNew->data = val;
		pTail->pNext = pNew;
		pTail = pNew;
		pTail->pNext = NULL;//初始化节点的指针域
	}
	return pHead;
}

PNODE MergeTwoList(PNODE p1, PNODE p2)
{if (p1 == NULL)//谁先为空便是递归的结束条件
		return p2;//返回p2的原因是使让最底层递归结束后将p2返回对上一层的p1->next赋值
	if (p2 == NULL)
		return p1;//返回p1的原因是使让最底层递归结束后将p1返回对上一层的p2->next赋值
	if (p1->data< p2->data)
	{p1->pNext = MergeTwoList(p1->pNext, p2);//谁小便移动谁，谁移动便返回谁以便于上一级节点连接
		return p1;
	}
	else
	{p2->pNext = MergeTwoList(p1, p2->pNext);
		return p2;
	}

}

void bianli(PNODE pHead)
{PNODE p = pHead->pNext;
	while (p)
	{printf("%d ", p->data);
		p = p->pNext;
	}
}

int main(void)
{	PNODE Head_1 = CreateList();
	PNODE Head_2 = CreateList();
	MergeTwoList(Head_1,Head_2);//也可以设立两个新的指针指向头结点
	bianli(Head_1);

	return 0;
}

同时我们需要注意例如p1->pNext = MergeTwoList(p1->pNext, p2);,我们是先对递归函数仅需调用再赋值，也就是说，当调用未结束时，p1->nexr一直未曾赋值，但虽然一直未赋值，但是像l1->next与l2->next一直在变化，所以递归结束后返回的是变化后的节点

递归结束后返回上一层断点处执行程序，未赋值的就先赋值

赋值后笔者还不知如何打印证明，但原理是这样的

递归返回的值是新赋值的值

五、递归的优缺点优点

为某些编程问题提供了简单的解决方案

缺点

会快速消耗计算机中的内存

总结

尽管初步了解了阶乘的使用，但是在平时做题可能一般想不到使用其方法，还是需要多做题巩固知识，下周的学习计划便以刷题为主，逐步巩固自己前面的知识

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

标题名称：递归的学习与应用-创新互联
文章网址：http://wjwzjz.com/article/djcscj.html

新网创想网站建设，新征程启航

递归的学习与应用-创新互联

其他资讯