递归简单举例_递归定义举例

递归简单举例_递归定义举例刚接触递归的同学,可能难以理解递归,难以理解的点可能很多,例如:1.函数为什么可以在自己的内部又调用自己呢?2.既然可以自己调用自己,那么递归运行过程中一定回有很多层相互嵌套,到底什么时候不再嵌套呢?3.递归运行过程中,相互嵌套的多层之间会有参数传递,多层之间是否会相互影响?递归两个要素1.递归边界2.递归的逻辑——递归”公式”递归的过程一定有参数的变化,并且参

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

刚接触递归的同学,可能难以理解递归,难以理解的点可能很多,例如:

1.函数为什么可以在自己的内部又调用自己呢?

2.既然可以自己调用自己,那么递归运行过程中一定回有很多层相互嵌套,到底什么时候不再嵌套呢?

3.递归运行过程中,相互嵌套的多层之间会有参数传递,多层之间是否会相互影响?


递归两个要素

1.递归边界

2.递归的逻辑——递归”公式”

递归的过程一定有参数的变化,并且参数的变化,和递归边界有关系.

在难度较大的题目中,这两者均不容易直接得到.


递归的种种问题,也许理解的同学可能可以用一句话解释清楚,但是不理解的同学再怎么说也没办法理解.

下面通过几个简单的例子【体会】一下递归,先从【感性】的角度理解递归.


1.Fibonacci数

我们直到Fibonacci数的递推公式为:F(0)=F(1)=1,F(n)=F(n-1)+F(n-2) n>=2;

这个明显地给出了递归边界n=0或1的时候F(n)的值,和递归逻辑F(n)=F(n-1)+F(n-2),即递推公式.所以这个递归函数不难书写

#include<iostream>
using namespace std;

int F(int n)//函数返回一个数对应的Fibonacci数
{
	if(n==0 || n==1)//递归边界
		return 1;
	return F(n-1) + F(n-2);//递归公式
}

int main()
{
	//测试
	int n;
	while(cin >> n)
		cout << F(n) << endl;

	return 0;
}

Jetbrains全家桶1年46,售后保障稳定



2.阶乘

阶乘的递归公式为:

递归简单举例_递归定义举例

代码如下:

#include<iostream>
using namespace std;

int F(int n)
{
	if(n==0)//递归边界
		return 1;

	return n*F(n-1);//递归公式
}

int main()
{
	int n;
	cin >> n;
	cout << F(n) << endl;

	return 0;
}


3.数组求和

给一个数组a[]:a[0],a[1],…,a[n-1]如何用递归的方式求和?

仍然是两个问题:递归边界和递归公式.

递归边界是什么?一时不容易想到,但是我们想到了求和,多个数的求和过程是什么,x,y,z,w手动求和的过程是什么?步骤如下:

x+y=a,任务变为a,z,w求和

a+z=b,任务变为b,w求和

b+w=c得出答案

思考一下,【得出答案】这一步为什么就可以得出答案呢?(废话?)是因为,一个数不用相加就能得出答案.

所以,递归的边界就是只有一个数.

所以,递归边界有了,那么递归公式呢?其实手动计算过程中,隐含了递归公式:

递归简单举例_递归定义举例

其中+为求两个数的和,F为求多个数的和的递归函数.代码如下:

#include<iostream>
using namespace std;

int F(int a[],int start,int end)
{
	if(start==end)//递归边界
		return a[start];

	return a[start] + F(a,start+1,end);//递归公式
}

int main()
{
	int a[] = {1,2,3,4,5};
	int s=0,e=4;
	cout << F(a,s,e) << endl;

	return 0;
}


4.求数组元素最大值

手动求最大值的过程是什么,遍历+比较,过程如下:

例如,求3,2,6,7,2,4的最大值:先设置最大值max=-999999,然后将max和数组元素逐个(遍历)比较如果a[i]>max,则更新max的值为a[i],否则max不变,继续向后遍历,直到遍历结束.

max<3,则max=3

max>2,max=3不变

max<6,则max=6

max<7,则max=7

max>2,max=7不变

max>4,max=7不变

遍历结束,max=7为最大值.

和求和类似,递归的公式如下:

递归简单举例_递归定义举例

其中max为求两个数的较大值函数,F为求多个数的最大值的递归函数.代码如下:

#include<iostream>
using namespace std;

#define max(a,b) (a>b?a:b)

int F(int a[],int s,int e)
{
	if(s==e)
		return a[s];
	else if(s+1 == e)//递归边界
		return max(a[s],a[e]);

	return max(a[s],F(a,s+1,e));//递归公式!!!
}

int main()
{
	int a[] = {5,1,4,6,2};
	int s = 0,e = 4;
	cout << F(a,s,e) << endl;

	return 0;
}

之所以,说上面的几个例子是【简单例子】,是因为上述所有的递归都属于【单向递归】.单向递归,递归的路径就是一个方向,所以思路相对比较容易想到.

较难的递归问题,一般都不是单向递归,而是需要使用【回溯】的方法,递归的方法不太容易想到.

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/219158.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 聊聊系统平均负载_什么是负载敏感系统

    聊聊系统平均负载_什么是负载敏感系统一、什么是平均负载单位时间内,系统处于可运行状态和不可中断状态的进程数,可简单理解为系统平均活跃进程数可运行状态:top命令状态为R,包括Runnable和Running不可中断状态:top命令状态为D,正处于内核态关键流程中的进程,并且这些流程是不可打断的,比如等待硬件设备的I/O响应,这往往是对数据一致性的一种保护机制二、如何查看平均负载$uptime…,loada…

  • java如何验证手机号码_Java 手机号码正则表达式验证「建议收藏」

    java如何验证手机号码_Java 手机号码正则表达式验证「建议收藏」1.正则表达式的字符串表示StringmobileRegex=”^1(3|4|5|7|8)\\d{9}$”;字符^意义:表示匹配的字符必须在最前边;字符$意义:表示待匹配串的结束位置;字符\d{5,9}意义:\d是数字,{5,9}是5-9位,如果只是验证手机号,且校验的正则表达式如下:/^1[3|5|8][0-9]\d{4,8}$/;不妨写成/^1[3|5|8]\…

  • java判断闰年的方法_Java判断闰年的2种方法示例|chu「建议收藏」

    java判断闰年的方法_Java判断闰年的2种方法示例|chu「建议收藏」前言:给定一个年份,判断这一年是不是闰年。当以下情况之一满足时,这一年是闰年:1.年份是4的倍数而不是100的倍数;2.年份是400的倍数。其他的年份都不是闰年。方法一:publicclassBissextile{booleanbissextile(intyear){//创建boolean类型的方法if(year%4==0&&year%1…

  • qtabwidget tab样式_qt geometry

    qtabwidget tab样式_qt geometrytabWidget=newQTabWidget();tabWidget->setUsesScrollButtons(true);//使QTabWidget显示滚动条tabWidget->setTabsClosable(true);//设置tab的关闭选项tabWidget->setTabsClosable(true)…

  • 阿里面试官:MySQL如何设计索引更高效?

    阿里面试官:MySQL如何设计索引更高效?这么问,我是真的没想到。。。

  • C++如何做字符串分割(5种方法)

    C++如何做字符串分割(5种方法)1、用strtok函数进行字符串分割原型:char*strtok(char*str,constchar*delim);功能:分解字符串为一组字符串。参数说明:str为要分解的字符串,delim为分隔符字符串。返回值:从str开头开始的一个个被分割的串。当没有被分割的串时则返回NULL。其它:strtok函数线程不安全,可以使用strtok_r替代。示例://借助strtok实现split#include<string.h>#include<stdio.h&

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号