首页 > 其他分享 >教你领悟函数递归的本质

教你领悟函数递归的本质

时间:2024-08-08 22:23:10浏览次数:14  
标签:return 函数 递归 int 打印 领悟 printf print

一、何为递归

①在C语言中,递归就是函数自己调用自己。递是指递推,归是指回归。
②递归的思想:将复杂的问题简单化。
③递推的两个必要条件。
a: 递归存在限制条件,当满足限制条件时,递归便不再继续
b:每一次递归都要越来越接近限制条件
/*用递归的方式求n!   (n>=0)*/
int Fact(int n)
{
	if (n <= 1)/*限制条件*/
	{
		return 1;
	}
	else
	{
		return n * Fact(n - 1);/*容易发现每一次递归都越来越接近限制条件*/
	}
}
int main()
{  
	int n = 0;
	scanf("%d", &n);
    int ret = Fact(n);
	printf("%d的阶乘是%d\n", n, ret);
	return 0;
}
④递归的层次不能太深。
每一次递归都是一次函数调用,需要向内存的栈区申请空间(这块空间被称为运行时堆栈,也叫函数栈帧),存放函数调用期间各种局部变量的值,当递归的次数足够多时,就会将栈区的空间占满,出现栈溢出(statck overflow
⑤递归的思想(大事化小
把⼀个⼤型复杂问题层层转化为⼀个与原问题相似,但规模较⼩的⼦问题来求解;直到⼦问题不能再被拆分,递归就结束了

二、递归的示例

/*输⼊⼀个正整数m,按照顺序打印正整数的每⼀位。
⽐如:
输⼊:1234 输出:1 2 3 4*/

/*方法1*/
void print(int m)
{
	/*若m是一位数,直接打印m */
	if (m <=9)
	{
		printf("%d ", m);
	}
		
	else/*如果m不是一位数,则先按顺序打印个位数之外的每一位,最后打印个位上的数*/
	{
		print(m / 10);
		printf("%d ", m % 10);
	}
}
/*方法一中的print函数稍稍有些繁琐,下面通过方法二将print函数进行简化*/


/*方法二: */
void print(int m)
{
	/*如果m不是一位数,则先按顺序打印个位数之外的每一位,再打印个位上的数
	  如果m是一位数,则直接打印m
	*/
	if (m > 9)/*递归的限制条件*/
	{
		print(m / 10);/*容易发现每一次递归都越来越接近限制条件*/
	}
	printf("%d ", m % 10);
}
int main()
{
	int m = 0;
	scanf("%d", &m);
	print(m);
	return 0;
}

三、不适合用递归的示例

(有些问题如果使用递归的方法求解,可能会由于递归的层次太深,导致计算量太大,使得程序在运行时需要耗费很长的时间才能得出最终的结果。这类问题使用递归的方法效率就很低)
示例如下:

在这里插入图片描述

那么像这类不适合用递归的方式求解的问题,该如何解决呢?
可以采用迭代的方式(通常指循环) 循环一定是迭代,但迭代不一定是循环
方法1:
int F(int n)
{
	int a = 1, b = 1, c = 0;
	if (n <= 2)
	{
		return 1;
	}
	else
	{
		for (int i = 1; i <= n - 2; i++)
		{
			c = a + b;
			a = b;
			b = c;
		}
		return c;
	}
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = F(n);
	printf("%d\n", ret);
	return 0;
}

方法1中的F(n)函数稍稍有些复杂,下面用通过另外一种方法对F(n)函数进行简化。
int F(int n)
{
	int a = 1, b = 1, c = 1;

	/*n=3时循环一次
	  n=4时循环两次
	  依此类推
	*/
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}

四、递归与迭代该怎么选呢

a. 如果一个问题用递归的方式求解非常简单,而且没有太大的问题,就可以选择用递归的方式
b. 但如果用递归的方式可能导致栈溢出,或者由于递归的层次太深,导致计算量太大时,就选择迭代的方式

标签:return,函数,递归,int,打印,领悟,printf,print
From: https://blog.csdn.net/2402_84440417/article/details/141034163

相关文章

  • FreeRTOS启动任务调度器函数解释
    目录vTaskStartScheduler()函数xPortStartScheduler()函数prvStartFirstTask()函数vPortSVCHandler()函数FreeRTOS的任务开始运行的前提是调用了启动调度器函数vTaskStartScheduler(),只有调用了该函数任务才会被调度并运行。下面以FreeRTOSv9.0.0版本的源码进行分析FreeRT......
  • C语言--函数
    函数的概述:函数:实现一定功能的,独立的代码模块。函数一定是先定义,后使用使用函数的优势:·我们可以通过函数提供功能给别人使用,也可以使用别人提供的函数,减少代码量               ·借助函数可以减少重复的代码               ·实现结构化(......
  • 轮换挑选图片,补充 es6的对象写法,uniapp使用,class和style,条件渲染,列表渲染,input
    Ⅰ轮换挑选图片【一】方式一<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>Title</title><scriptsrc="./js2/vue.js"></script></head><body>......
  • Java方法06:递归
    A方法调用B方法,我们很容易理解!递归就是:A方法调用A方法!就是自己调用自己,因此我们在设计递归算法时,一定要指明什么时候自己不调用自己。否则,就是个死循环!递归算法重点:递归是一种常见的解决问题的方法,即把问题逐渐简单化。递归的基本思想就是“自己调用自己”,一个使用递归技术的方......
  • 目录函数以及链接文件
    一、stat补充1、getpwuid()structpasswd*getpwuid(uid_tuid);功能:根据用户id到/etc/passwd文件下解析获得结构体信息参数:uid:用户id返回值:成功返回id对应用户的信息失败返回NULL2、getgrgid()structgroup*getgrgid(gid_tgid);拿到组的结构体功能:根据gid......
  • 递归调用生成部门的所有子部门
    1、样例publicclassDepartmentService{publicstaticvoidmain(String[]args){Map<String,Dept>deptMap=newHashMap<>();deptMap.put("研发部",newDept("研发部","A公司"));deptMap.put(&q......
  • 函数不声明也可调用
    目录一、编译试试二、说明原由编译器隐式声明三、总结四、源码一、编译试试1、main.c2、add.c3、编译执行二、说明原由编译器隐式声明gcc编译器在编译源文件时,遇到未声明的函数调用时,会根据函数调用时传入的参数类型隐式的为此源文件生成一个函数声明:函数参数......
  • FFmpeg源码:av_realloc、av_reallocp、size_mult、av_realloc_f函数分析
    =================================================================FFmpeg内存管理相关的源码分析:FFmpeg中内存分配和释放相关的源码:av_malloc函数、av_mallocz函数、av_free函数和av_freep函数分析FFmpeg源码:av_realloc、av_reallocp、size_mult、av_realloc_f函数分析FF......
  • Pandas高级操作:多级索引、窗口函数、数据透视表等
            在数据处理和分析中,pandas库提供了强大的功能,支持从简单到复杂的数据操作。本文将介绍一些pandas的高级操作,包括多级索引(MultiIndex)、窗口函数(WindowFunctions)、数据透视表与复杂聚合、数据合并与连接、高级数据变换以及时间序列数据的高级处理。1.多级索......
  • 【Python】excel常用函数操作Python实现,办公入门首选
    常见的Excel函数,在Python中的如何实现:VLOOKUP:可以使用merge或map函数来实现类似的功能。IF:可以使用numpy库的where函数来实现类似的功能。SUMIF:可以使用pandas的query函数来筛选数据,然后使用sum函数来计算总和。COUNTIF:类似于SUMIF,可以使用query函数来筛选数据,然......