函数递归专题(案例超详解&&一篇讲通透)

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

前言

程序调用自身的编程技巧称为递归( recursion)。
递归做为一种算法在程序设计语言中广泛应用。
一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。
递归策略
只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。
递归的主要思考方式在于把大事化小

递归的两个必要条件

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

1.递归案例:

案例一:取球问题

在 n 个球中,任意取 m 个(不放回),求有多少种不同取法。

分析:

假设有一个特殊球,此球的状态只有两种:被取到和没有被取到。
若被取到,那么只需在n-1个球中取m-1个球。
若没有被取到,需在n-1个球中取m个球。

代码演示: 
int ball(int n, int m)
{
	if (m > n)
		return 0;
	if (n == m)
		return 1;
	if (m == 0)
		return 1;
	return ball(n - 1, m - 1) + ball(n - 1, m);
}
int main()
{
	int n = 0;
	int m = 0;
	scanf("%d%d", &n, &m);
	printf("%d\n", ball(n, m));
	return 0;
}

运行结果:
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

案例二:求斐波那契额数列

这个数列从第3项开始,每一项都等于前两项之和。

分析:

在数学上,斐波那契数列以如下被以递推的方法定义:
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

代码演示:
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);//20
	int ret = Fib(n);
	printf("%d\n", ret);
	return 0;
}

运行结果:
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

案例三:函数实现n的k次方

分析

函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言
指数为负数用double(%lf打印)

代码演示:
double Pow(n, k)
{
	if (k > 0)
	{
		return n * Pow(n, k-1);
	}
	else if(k == 0)
	{
		return 1;
	}
	else
	{
		return 1.0 / Pow(n, -k);//实现指数为负数
	}

}
int main()
{
	int n = 0;
	int k = 0;
	scanf("%d %d", &n, &k);
	double ret = Pow(n, k);
	printf("%lf\n", ret);//double打印用lf
	return 0;
}

运行结果:
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

案例四:输入一个非负整数,返回组成它的数字之和

分析:

当一个数是大于0 的数时,要得结果等于这个数模(%)10得到最低位的数字,然后再加它的次低位…一直加到最高位的数字,这些数字用给这个数除以(10)得到,递归调用这个函数,即可。

代码演示:
int DigitSum(int n)
{
	if (n < 9)
	{
		return n;
	}
	else
	{
		return DigitSum(n / 10) + n % 10;
	}
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = DigitSum(n);
	printf("%d\n", ret);
	return 0;
}

运行结果:
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

案例五:元素逆置

分析:

函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

代码演示:
#include<string.h>
void reverse_string(char* str)
{
	size_t len = strlen(str);
	char temp = str[0];
	str[0] = str[len - 1];
	str[len - 1] = '\0';
	if (strlen(str+1) >= 2)
	{
		reverse_string(str+1);
	}
	str[len - 1] = temp;
}
int main()
{
	char arr[] = "abcdef";
	reverse_string(arr);
	printf("%s\n", arr);//字符串用%s打印
	return 0;
}

运行结果:
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

案例六:实现strlen

分析:

函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

代码演示:
size_t my_strlen(char* str)
{
	if (*str == '\0')//(str==0)
		return 0;
	else
		return 1 + my_strlen(str + 1);
}
int main()
{
	char arr[] = "abcdef";
	size_t len = my_strlen(arr);
	printf("%zd", len);
	return 0;
}

运行结果:
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

案例七:爬楼梯1.0

树老师爬楼梯,他可以每次走 1 级或者 2 级,输入楼梯的级数,求不同的走法数。

分析:

如果从第0级台阶爬到第1级台阶:有1种方法(爬1个台阶)
如果从第0级台阶爬到第2级台阶:有2种方法(爬1个台阶 或 爬2个台阶)
如果从第0级台阶爬到第3级台阶:有3种方法
先从第0级台阶爬到第1级台阶,再从第1级台阶爬到2级台阶,再从第2级台阶爬到第3级台阶,即1,1,1
先从第0级爬1个台阶到第1级台阶,再从第1级爬2个台阶到第3级,即1,2
先从第0级爬2个台阶到第2级台阶,再从第2级爬1个台阶到第3级,即2,1
如果从第0台阶爬到第4级台阶:有5种方法
1,1,1,1
1,1,2
1,2,1
2,1,1
2,2
归纳发现原理同:斐波那契数列

代码演示:
int stair(int n)
{
	if (n == 1)
		return 1;
	if (n == 2)
		return 2;
	return stair(n - 1) + stair(n - 2);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d\n", stair(n));
	return 0;
}

运行结果:
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

案例八:爬楼梯2.0

树老师爬楼梯,他可以每次走 1 级、2 级或者 3 级,输入楼梯的级数,求不同的走法数。

原理同上

代码演示:
int stair(int n)
{
	if (n == 1)
		return 1;
	if (n == 2)
		return 2;
	if (n == 3)
		return 4;
	return stair(n - 1) + stair(n - 2) + stair(n - 3);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d\n", stair(n));
}

运行结果:
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

案例九:求阶乘
代码演示:
int Fac(int n)
{
	if (n <= 1)
		return 1;
	else
		return n* Fac(n - 1);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int r = Fac(n);
	printf("%d\n", r);

	return 0;
}

运行结果:
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

案例十:求阶乘和

求 1!+2!+3!+4!+5!+6!+7!+…+n!的和。

代码演示:
int factorial(int n)
{
	if (n == 1)
		return 1;
	return n * factorial(n - 1);
}
int main()
{
	int n = 0;
	int sum = 0;
	int i = 0;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
	{
		sum += factorial(i);
	}
	printf("%d\n", sum);
	return 0;
}

运行结果:
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

案例十一:杨辉三角

输入要打印的层数,打印杨辉三角
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

分析

根据观察第一列和对角线上的元素之外,其余元素的值均为前一行上的同列元素和前一列元素之和。(我们可以依靠递归相加就行实现)

#include <stdio.h>
long Tri(int r, int c)    
{
    return (c == 1 || c == r) ? 1 : Tri(r - 1, c - 1) + Tri(r - 1, c);
}
int main()
{
    int i = 0;
    int j = 0;
    int n = 0;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)	// 输出n行
    {
        for (j = 0; j < n - i; j++)		//每行前面补空格,显示成等腰三角形	
            printf("   ");
        for (j = 1; j <= i; j++)
            printf("%6d", Tri(i, j));	//计算并输出杨辉三角形	
        printf("\n");
    }
    return 0;
}

运行结果:
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

案例十二:最大公约数
//代码演示:
int gcd(int a, int b)
{
	int t = 0;
	if (a < b)
	{
		t = a;
		a = b;
		b = t;
	}
	if (b == 0)
		return a;
	return gcd(b, a % b);
}
int main()
{
	int a = 0;
	int b = 0;
	scanf("%d%d", &a, &b);
	printf("%d\n", gcd(a, b));
	return 0;
}

运行结果:
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

案例十四:汉偌塔

汉诺塔问题就是将A柱上n个圆全部移动到C上,过程中可以借助B柱,但要始终保持小圆在大圆上面
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

对于n阶汉诺塔的移动次数:

函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
int main()
{
	int num = 0;
	scanf("%d", &num);//塔数
	printf("完成%d层的汉诺塔需要%d步\n", num, (int)pow(2,num) - 1);
	return 0;
}

运行结果:
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

分析:

步骤1所含步数就是n-1个圆盘移动所需的次数,我们可以将其步数看做f(n-1)。
步骤2所含步数为1。
步骤3所含步数与步骤1相似,我们也将其步数看做f(n-1)。
再观察表格中汉诺塔的移动次数,对于一阶汉诺塔移动次数就为1,对于其他的阶数则为前一阶汉诺塔移动次数 + 1 + 前一阶汉诺塔移动次数。

不难得出递推表达式:f(n-1) + 1 + f(n-1) = 2 * f(n - 1) + 1

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int Hanio_twice(int num)
{
	if(1 == num)
		return 1;
	else
		return 2 * Hanio_twice(num - 1) + 1;
}
int main()
{
	int num = 0;	
	scanf("%d", &num);//塔数
	int ret = Hanio_twice(num);
	printf("完成%d层的汉诺塔需要%d步\n", num, ret);
	return 0;
	}

运行结果:
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

分析:

我们观察移动步骤,发现只有一个圆盘时移动步骤为A->C;两个圆盘时,为A->B,A->C,B->C。
那么对于n阶汉诺塔呢,我们对其进行推演:
1.把n-1个圆盘从A移动到B
2.把第n个圆盘从A移动到C
3.把n-1个圆盘从B移动到C
那n-1个圆盘如何从A移动到B呢?
1.把n-2个圆盘从A移动到C
2.把第n-1个圆盘从A移动到B
3.把n-2个圆盘从C移动到B
同样的,对于把n-1个圆盘从B移动到C,也可以推测出来:
1.把n-2个圆盘从B移动到A
2.把第n-1个圆盘从B移动到C
3.把n-2个圆盘从A移动到C
通过这些推演我们发现,汉诺塔的移动可以通过递归展开,那么以上推演步骤,我们可以将其作为递归的步骤。

思路:定义A,B,C三个字符,表示A,B,C三柱,定义n为阶数,那么n-1也就是移动步骤中,需要移动的圆盘数。
对于一阶汉诺塔,直接移动即可,对于其他的阶数,则需要通过递归展开,为n阶汉诺塔的移动步骤。函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

//代码演示:
void move(char pos1, char pos2)
{
	printf(" %c -> %c \n", pos1, pos2);
}
//pos1起始位置
//pos2中转位置
//pos3目标位置
void Hannoi(int n, char pos1, char pos2, char pos3)
{
	if (n == 1)
	{
		move(pos1, pos3);
	}
	else
	{
		Hannoi(n - 1, pos1, pos3, pos2);
		move(pos1, pos3);
		Hannoi(n - 1, pos2, pos1, pos3);
	}
}
int main()
{
	/*Hannoi(1, 'A', 'B', 'C');*/
	//Hannoi(2, 'A', 'B', 'C');
	Hannoi(3, 'A', 'B', 'C');
	return 0;
}

运行结果:
函数递归专题(案例超详解&&一篇讲通透),算法,开发语言,c语言

2.递归与迭代

听过上面函数递归案例发现有问题,如下:

在使用 Fib 这个函数的时候如果我们要计算第50个斐波那契数字的时候特别耗费时间。
使用 Fac 函数求10000的阶乘(不考虑结果的正确性),程序会崩溃。

为什么呢?

我们发现 Fib 函数在调用的过程中很多计算其实在一直重复。

那我们如何改进呢?

在调试 Fac 函数的时候,如果你的参数比较大,那就会报错: **stack overflow(栈溢出)**这样的信息。
系统分配给程序的栈空间是有限的,但是如果出现了死循环,或者(死递归),这样有可能导致一直开辟栈空间,最终产生栈空间耗尽的情况,这样的现象我们称为栈溢出。

那如何解决上述的问题:

将递归改写成非递归。
使用static对象替代 nonstatic 局部对象。在递归函数设计中,可以使用 static 对象替代nonstatic 局部对象(即栈对象),这不仅可以减少每次递归调用和返回时产生和释放 nonstatic 对象的开销,而且 static 对象还可以保存递归调用的中间状态,并且可为各个调用层所访问。

比如,下面代码就采用了,非递归的方式来实现:

n的阶乘

int Fac(int n)
{
	int i = 0;
	int r = 1;
	for (i = 1; i <= n; i++)
	{
		r = r * i;
	}
	return r;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int r = Fac(n);
	printf("%d\n", r);

	return 0;
}

求第n个斐波那契数

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);//20
	int ret = Fib(n);
	printf("%d\n", ret);
	return 0;

3.何时使用递归

如果使用递归很容易想到,写出的代码没有明显的缺陷,那我们就可以使用递归
但如果写出的递归代码,有明显问题,比如:栈溢出,效率低下等,那我们还是使用迭代的方式来解决.

💘本次专题已结束,不久将来会有更多专题与大家见面!!!文章来源地址https://www.toymoban.com/news/detail-651568.html

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

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

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

相关文章

  • 递归、搜索与回溯算法(专题二:深搜)

    往期文章(希望小伙伴们在看这篇文章之前,看一下往期文章) (1)递归、搜索与回溯算法(专题零:解释回溯算法中涉及到的名词)【回溯算法入门必看】-CSDN博客 (2)递归、搜索与回溯算法(专题一:递归)-CSDN博客  深搜是实现递归的一种方式,接下来我们之间从题

    2024年01月20日
    浏览(81)
  • 递归专题训练详解(回溯,剪枝,深度优先)

    在经典汉诺塔问题中,有 3 根柱子及 N 个不同大小的穿孔圆盘,盘子可以滑入任意一根柱子。一开始,所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制: (1) 每次只能移动一个盘子; (2) 盘子只能从柱子顶端滑出

    2024年02月07日
    浏览(46)
  • 递归、搜索与回溯算法(专题六:记忆化搜索)

    目录 1. 什么是记忆化搜索(例子:斐波那契数) 1.1 解法一:递归 1.2 解法二:记忆化搜索 1.2.1 记忆化搜索比递归多了什么? 1.2.2 提出一个问题:什么时候要使用记忆化搜索呢? 1.3 解法三:动态规划 1.3.1 先复习一下动态规划的核心步骤(5个),并将动态规划的每一步对应

    2024年01月20日
    浏览(48)
  • 【C++】递归,搜索与回溯算法入门介绍和专题一讲解

    个人主页:🍝在肯德基吃麻辣烫 我的gitee:C++仓库 个人专栏:C++专栏 从本文开始进入递归,搜索与回溯算法专题讲解。 递归就是函数自己调用自己。 递归的本质是: 主问题:—相同的子问题 子问题:—相同的子问题 通过: 1)通过递归的细节展开图(前期可以,过了前期

    2024年02月09日
    浏览(37)
  • python案例——函数递归案例

    问题描述: 一个猴子第一天吃掉桃子的一半又多一个,第二天照此方法又吃掉剩下一半加一个,以后每天如此,直到第十天早上,只剩下了一个桃子,问第一天原本多少个桃子 代码实现: 问题描述: 打印杨辉三角形   算法设计: 杨辉三角形中的数正好是(x+y)的N次幂的展

    2024年02月05日
    浏览(42)
  • 递归函数的介绍及使用案例

    递归函数,实际上就是将一个自定义的函数在运行过程中反复调用他自己,直到遇到结束条件就停止

    2024年02月08日
    浏览(40)
  • 【C语言】万字教学,带你分步实现扫雷游戏(内含递归函数解析),剑指扫雷,一篇足矣

    君兮_的个人主页 勤时当勉励 岁月不待人 C/C++ 游戏开发 Hello,这里是君兮_,今天更新一篇关于利用C语言实现扫雷游戏的博客。对于初学者来说,这也是一个非常容易上手的小项目,看完不妨自己试试哦! 废话不多说,我们直接开始吧! 相信很多人在小时候都玩过扫雷游戏,但

    2024年02月11日
    浏览(42)
  • 前端vue后端go如何进行跨域设置?一篇就通透理解

    跨域 (Cross-Origin)指的是在 浏览器 中,当一个 web 应用程序试图访问 不同域名、不同端口或不同协议的资源时,就会发生跨域请求 ,此时浏览器的 同源策略 (Same-Origin Policy)就会进行拦截,他是同源策略是一种 安全机制 ,它限制了网页中的 JavaScript 代码只能访问同源(

    2024年04月12日
    浏览(47)
  • 函数递归详解

    函数递归是一种算法,递归是通过将问题分解为更小的子问题来解决问题的办法,递归的优点如下: 简洁性:递归可以用较少的代码实现复杂的功能 灵活性:递归可以应对未知深度的数据结构,因为它不需要提前知道要处理的嵌套层级 递归 : 程序调用自身的编程技巧称为

    2024年02月07日
    浏览(31)
  • 函数递归(详解)

    首先我们可以 从字面上来解释一下 : 递归的 递 :可以理解为 递推 递归的 归 :可以理解为 回归 接下来我们来看看递归的定义: 程序调用自身的编程技巧称为递归 ( recursion)。 递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在 其定义或说明中有直接或

    2024年02月12日
    浏览(32)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包