递归算法的简单解析
2021/10/16 17:12:18
本文主要是介绍递归算法的简单解析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录
文章目录
前言
一、递归的定义
二、递归的基本思想
三.递归的条件
四、递归的应用
1.汉诺塔问题
2.二分查找
3.斐波拉契数列的求值
前言
很多同学对于理解递归这种算法感到困惑,感觉有一种说不清,道不明的感觉,或许大多数初学者都会有这样的疑惑,但是递归算法在我们的生活中无时无刻不在体现,这种递归算法大抵就像一只纸糊的拦路虎,读者细细品味,便可理解。
提示:以下是本篇文章正文内容,下面案例可供参考
一、递归的定义
递归定义:若一个算法直接或间接地调用自己本身,则称这个算法是递归算法
二、递归的基本思想
在学习到阶乘时,常常会遇到计算某个数的阶乘,例如计算5!通常像下面会用循环去做
void jiechen() { int x = 1; for (int i = 1; i <= 5; i++) { x = x * i; } printf("%d\n", x); }
其实对于阶乘的问题用递归的思路依然可以
int main() { printf("5的阶乘是%d", jiechen(5)); return 0; } int jiechen(int n) { if (n <= 1) return n; else return n * jiechen(n - 1); }
通过对上面例子的举例,不难看出,递归无非就是不断地调用自己罢了,可以更加简单的理解为,在执行函数调用时,调用了一个跟自己长得一模一样的函数,功能也一样
从这个问题中不难看出,阶乘所执行的只是简单重复的机械运动,那对于一个问题来说,什么时候我们会用到这种递归的方法呢?
三.递归的条件
在递归的算法中,我们实际上解决的是将一个简单的运动重复n次的过程,是一个将一顿代码循环n次的过程,那为什么我们还要用这种算法呢?其实在后面数据结构的学习中,面对一些非线性结构时,我们的查找和遍历就需要这种方法。 对于一段重复的代码来说,其实还有一个问题我们应该注意,对于循环来说,我们需要有循环的条件,那对于递归,我们应该设置一个“出口”,要不然陷入到无限的调用自己中去,也是没有什么意义。
综上所述,递归的条件:
(1)简化后的问题与原问题有着相同的解决形式。
(2)递归必须有简洁的退出条件。
四、递归的应用
1.汉诺塔问题
解题思路:对于一个盘来说,我们只需将此盘从A移动到C上,对于两个盘子,我们需要先借助B,把第一个小的移动到B,再将第二个移动到C上,最后将第一个从B中移动到C中,对于n个盘子来说,可以将其看做是两个盘子,一个盘子是n,另外是由另外(n-1)个盘子所构成的一个盘子,那么移动的步骤如下:
1.将(n-1)个盘子从A移动到B上
2.将第n个盘子从A移动到C上
3.将(n-1)个盘子从B移动到C上
具体代码如下
void test01() { printf("请输入现在有几个盘子:\n"); int n; scanf_s("%d", &n); tower(n, 'A', 'C', 'B'); } /*n 是盘子个数,frompeg是A,topeg是C,auxpegB*/ void tower(int n, char frompeg, char topeg, char auxpeg) { if (n == 1) /*设置递归出口*/ { printf("%s%c%s%c\n", "move disk 1 from peg ", frompeg, " to peg ", topeg); return; } /*将(n-1)个盘子借助 C 从 A 移动到 B 上*/ tower(n - 1, frompeg, auxpeg, topeg); /*将盘子n从 A 移动到 C 上*/ printf("%s%d%s%c%s%c\n", "move disk ", n, " from peg ", frompeg, " to peg ", topeg); /*将(n-1)个盘子借助 A 从 B 移动到 C 上*/ tower(n - 1, auxpeg, topeg, frompeg); }
2.二分查找
解题思路:在一半的中去寻找另一半,直至找到为止
/*a[]数组a,x是查找的元素,low是查找的起点,high 是查找的终点*/ int chazhao(int a[], int x, int low, int high) { int mid; mid = (high + low) / 2; /*二分的中点*/ if (a[mid] == x) return mid; else if (x < a[mid]) /*在二分中点的左边*/ return chazhao(a, x, low, mid - 1); else /*在二分中点的右边*/ return chazhao(a, x, mid + 1, high); }
3.斐波拉契数列的求值
解题思路:对于斐波拉契数列,很明显的特征就是从n>1开始,第三项等于前两项之和,也就是说,对于n=0,n=1来说是不满足递归的条件的,所以需要一点分类讨论
具体代码如下
void test03() { int n; printf("请输入n的值是多少:\n"); scanf_s("%d", &n); if(n<=1) { printf("n= %d 时值为 %d \n", n, n); } else printf("n= %d 时值为 %d \n", n, jisuan(n-2,0,1,0)); } /*n表示第n项的值 before是第前两项的值,after第前一项的值,current是现在的值*/ int jisuan(int n,int before,int after,int current) { current = before + after; /*前两项相加*/ before = after; /*新的第前两项的值*/ after = current; /*新的第前一项的值*/ if (n == 0) return current; /*递归的条件是n==0,结果是返回current的值*/ jisuan(n - 1, before, after, current); }
总结
对于递归算法,最复杂的不是其过程,递归的过程只是简单的一个重复运动而已,而真正的关键在于我们是否能够在不同实际问题中抽象出这种思路!
这篇关于递归算法的简单解析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-22项目:远程温湿度检测系统
- 2024-12-21《鸿蒙HarmonyOS应用开发从入门到精通(第2版)》简介
- 2024-12-21后台管理系统开发教程:新手入门全指南
- 2024-12-21后台开发教程:新手入门及实战指南
- 2024-12-21后台综合解决方案教程:新手入门指南
- 2024-12-21接口模块封装教程:新手必备指南
- 2024-12-21请求动作封装教程:新手必看指南
- 2024-12-21RBAC的权限教程:从入门到实践
- 2024-12-21登录鉴权实战:新手入门教程
- 2024-12-21动态权限实战入门指南