函数递归详解

这篇具有很好参考价值的文章主要介绍了函数递归详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言:

函数递归是一种算法,递归是通过将问题分解为更小的子问题来解决问题的办法,递归的优点如下:

  • 简洁性:递归可以用较少的代码实现复杂的功能
  • 灵活性:递归可以应对未知深度的数据结构,因为它不需要提前知道要处理的嵌套层级

什么是递归?

递归程序调用自身的编程技巧称为递归

  • 从调用自身的层面:函数递归就是自己调用自己
  • 从编程技巧层面:一种方法(它通常将一个大型复杂问题层层转化为一个与原问题相似的规模较小的问题来求解,简化程序的代码量),这种方法的主要思想为:将大事化小

史上最简单的递归:

int main()
{
	printf("hehe\n");

	main();

	return 0;
}

 main()函数内部调用了main()函数,产生的现象为程序死递归,导致栈溢出(stack overflow);

递归的两个必要条件

  1. 存在限制条件,当满足这个限制条件的时候,递归便不再继续;
  2. 每次递归调用之后越来越接近这个限制条件;

递归的细节说明

  • 每一级递归都有自己的参数,参数形式可能相同,但是其值不同

函数调用之前,操作系统会为其分配函数栈帧,从而保留函数调用时当前函数的参数

  • 每一次函数调用结束都要返回值,当递归执行结束后,控制权转回到上一级函数

当递归的最后一层执行结束,系统释放最后一次递归调用所开辟的空间,同时返回到上一级函数调用,接着向下执行程序,当上一级递归结束,系统继续释放该级调用的函数栈帧,按此循环,直至系统回收主函数所开辟的函数栈帧为止;

  • 函数中递归语句之前的代码,按被调函数的顺序执行,递归之后的代码,与被调函数相反的顺序执行

递归示例

示例1:

接受一个整型值(无符号),按照顺序打印它的每一位

输入:1234           输出:1 2 3 4

思路:

假设定义print()函数,其功能为按照顺序打印每一位

print(1234)即打印1 2 3 4

print(123)  4 按照顺序打印1 2 3,最后打印4;

print(12)   3  按照顺序打印1 2 ,最后打印3;

printf(1)    2  打印1,最后打印2;

当位数只有一位时,不需要进行拆分,直接打印;

//只需要打印,不需要返回值
void print(unsigned int x)
{
	if (x > 9)
	{
		print(x / 10);//剥离n位数的前n-1位
	}
	printf("%d ", x % 10);//打印最后一位
}
int main()
{
	unsigned int num = 0;
	scanf("%d", &num);
	print(num);
	return 0;
}

运行结果:

函数递归详解,算法

画图分析:程序执行过程如箭头所示

函数递归详解,算法

示例2:

  • 求字符串长度
int my_strlen(char* s)
{
	int count = 0;
	while (*s != '\0')
	{
		count++;
		s++;
	}
	return count;
}
int main()
{
	char arr[] = "abc";
	int len = my_strlen(arr);
	printf("%d\n", len);
	return 0;
}
  • 编写函数不允许创建临时变量,求字符串长度

思路:

假设my_strlen()函数可以求字符串长度,参数为字符指针

传参时需要传址,对字符地址进行解引用操作,如果第一个字符就是'\0',长度为0

如果第一个字符不是'\0',长度为1+my_strlen()函数;

例如:

my_strlen("abc")

1+my_strlen("bc")

1+1+my_strlen("c")

1+1+1+my_strlen("")

int my_strlen(char* s)
{

	if (*s == '\0')
		return 0;
	else
		return 1 + my_strlen(s + 1);
}
int main()
{
	char arr[] = "abc";
	int len = my_strlen(arr);
	printf("%d\n", len);
	return 0;
}

   示例3:

  • 求第n个斐波那契数

思路:

斐波那契数列:1  1   2   3    5    8   13   21   34    55  ......

斐波那契数的特点前两个数的和等于第三个数

 公式:

     当n<=2时,   Fib(n)=  1

     当n>2时,     Fib(n)= Fib(n-1)+Fib(n-2)

//递归解法
int Fib(int n)
{
	if (n <= 2)
		return 1;
	else
		return Fib(n - 1) + Fib(n - 2);
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d\n", ret);
	return 0;
}

 递归的方式求解斐波那契数存在大量重复的计算,导致性能下降,效率低下,解决方案:

采用非递归方式求解

思路:

利用斐波那契数的特点,前两个斐波那契数不用计算

a=1 b=1 c=a+b=2

a=b=1  b=c=2 c=a+b=1+2=3

a=b=2   b=c=3  c=a+b=5

......

//迭代解法
//前两个斐波那契数不用计算,计算第n个斐波那契数即程序执行n-2次
int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;

	while (n >= 3)
	{
		c = a + b;
		a = b;
		b = c;

		n--;
	}
	return c;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d\n", ret);
	return 0;
}

 文章来源地址https://www.toymoban.com/news/detail-733624.html

到了这里,关于函数递归详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Python基础算法训练——函数与递归(46~50)

    Python基础算法训练——函数与递归(46~50) 46. 数字统计 【题目描述】 请统计某个给定范围 [L,R] 的所有整数中,数字 7 出现的次数。 比如给定范围 [60,80] 中,7一共出现12次。分别是67,77的个位,以及 70∼79 的十位。 【输入】 一行两个数 L,R 表示范围,用空格分隔。 【输出】 一

    2024年02月15日
    浏览(58)
  • 函数递归专题(案例超详解&&一篇讲通透)

    程序调用自身的编程技巧称为递归 ( recursion)。 递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。 递归策略 只需少量

    2024年02月12日
    浏览(48)
  • c语言基础知识帮助理解(函数递归详解)

    \\\"从前有座山,山里有座庙,庙里有个老和尚和一个小和尚。有一天老和尚对小和尚说:“从前有座山.山里有座庙,庙里有个老和尚和一个小和尚,有一天老和尚对小和尚说:“从前有座山.山里有座庙,庙里有个老和尚和一个小和尚......\\\" (虽能体现递归特点,但又不是递归)

    2024年02月14日
    浏览(39)
  • 你是真的“C”——函数递归详解青蛙跳台阶

       哈喽!😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不多说,文章推上!欢迎大家在评论区唠嗑指正,觉得好的话别忘了一键三连哦!😘 青蛙跳台阶问题简述: 😍     一只青蛙可以一次跳 1 级台阶或一次跳 2 级台阶 。例如

    2024年02月02日
    浏览(46)
  • 计算二叉树深度算法(递归、非递归)入门详解

    一、引言 二叉树在应用时,经常需要知道二叉树的深度。二叉树的深度就是二叉树的层数,即从树根算起,到最底下一层的层数是多少,即二叉树中结点的最大层次值。 本文给出了计算二叉树深度的算法,包括递归算法和非递归算法。 二、计算二叉树的基本方法 如下图所示

    2024年01月17日
    浏览(41)
  • 递归算法详解与应用

    本文深入解析了递归算法,包括递归实现指数型枚举、排列型枚举、组合型枚举的原理和代码实现。同时介绍了使用next_permutation()函数来枚举全排列的方法。

    2023年04月27日
    浏览(44)
  • Python递归算法详解

      递归是一种常见且重要的算法设计和解决问题的方法。它通过将问题分解为规模更小的子问题,并通过解决子问题来解决原始问题。递归算法的关键在于找到递归终止条件和递归调用的方式。本文将介绍递归的基本原理、应用场景,并通过相关的Python代码示例详细讲解递归

    2024年02月05日
    浏览(32)
  • 二叉树遍历之中序遍历算法(非递归、递归)入门详解

    一、引言 二叉树的遍历常见的方法有先序遍历、中序遍历、后序遍历和层次遍历等,本文给出了C语言版本的中序遍历二叉树的非递归算法和递归算法。 中序遍历的原理很简单,也就是把树根的访问放在中间。访问结点的次序是:“左—根—右”,也就是首先访问左子树,之

    2024年02月06日
    浏览(44)
  • [排序算法]:归并排序(Merge Sort)(递归与非递归实现详解)

            归并排序,是创建在归并操作上的一种有效的排序算法。算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。归并排序思路简单,速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列。

    2024年01月20日
    浏览(45)
  • c++详解递归算法-全网最全+例题讲解

    什么是递归? 递归的思想是什么? 什么时候该用递归? 使用递归需要注意哪些问题? 递归思想解决经典问题 递归和循环的区别是什么? 递归算法: 定义:直接或间接地出现对自身的调用 本质:递归即 递进 与 回归, 基本思想就是把规模大的问题转化为规模小的相似的子

    2024年02月07日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包