简单了解函数递归

server/2024/12/25 13:23:42/

函数递归

  • 一 了解函数递归
  • 二 深入理解函数递归的思想
  • 三 函数递归的优缺点

一 了解函数递归

首先,我们通过一个简单的代码来理解函数递归。

#include<stdio.h>
int Func()
{return Func(n+1);
}
int main()
{int n = 5;Func(n);return 0;
}

这个就是函数递归,简单来说就是函数自己调用自己。

二 深入理解函数递归的思想

下面,以求n的阶乘为例,来更加深入的了解函数递归。

n的阶乘就是1~n的数字累积相乘,我们知道n的阶乘的公式:n! = n ∗ (n − 1)! ,回归到这个公式的本来的推导过程,
在这里插入图片描述
也就是n!—>n*(n-1)!
(n-1)!—>(n-1)*(n-2)!
……
直到n是1或者0时,不再拆解
再稍微分析⼀下,当 n<=1 的时候,n的阶乘是1,其余n的阶乘都是可以通过上述公式计算。
n的阶乘的递归公式如下:
在这里插入图片描述
部分代码如下:

int Fact(int n)
{if(n<=0)return 1;elsereturn n*Fact(n-1);
}

测试代码:

#include <stdio.h>
int Fact(int n)
{if(n<=0)return 1;elsereturn n*Fact(n-1);
}
int main()
{int n = 0;scanf("%d", &n);int ret = Fact(n);printf("%d\n", ret);return 0;
}

运行结果:在这里插入图片描述
画图推演:
在这里插入图片描述

在求n的乘方的推导过程中,我们发现,这样的思路就是把⼀个较⼤的问题,转换为⼀个与原问题相似,但规模较⼩的问题来求解的,也就是递归的大事化小思想。
另外,函数递归是有限制条件的,对于求n的阶乘这个问题,我们发现它的限制条件是n是1或者0时,不再拆解,并且递归的过程,n在不断的趋近1或0。

三 函数递归的优缺点

对于递归,其好处就是用少量的代码解决复杂的问题,如果以迭代的方式解决这个问题,我们会感觉代码量明显增加。


#include<stdio.h>
int main()
{int n = 0;scanf("%d", &n);int ret = 1;if (n <= 1){ret = 1;printf("%d\n", ret);}else{for (int i = 2; i <= n; i++){ret *= i;}printf("%d\n", ret);}return 0;
}

但这并不是说递归就一定是好的,递归中,只要有函数调用,就会分配空间,递归会消耗一定的空间,还要注意递归是否栈溢出(stackoverflow)。
我们也能举出更加极端的例⼦,就像计算第n个斐波那契数,是不适合使⽤递归求解的,但是斐波那契数的问题通过是使⽤递归的形式描述的,如下:
在这里插入图片描述
看到这公式,很容易诱导我们将代码写成递归的形式,如下所⽰:

int Fib(int n){if(n<=2)       return 1;  else      return Fib(n-1)+Fib(n-2);
}
#include <stdio.h>
int main()
{int n = 0;scanf("%d", &n);int ret = Fib(n);printf("%d\n", ret); return 0;
}

可是,当我们n输⼊为50的时候,需要很⻓时间才能算出结果,这个计算所花费的时间,是我们很难接受的,这也说明递归的写法是⾮常低效的,那是为什么呢?
在这里插入图片描述

其实递归程序会不断的展开,在展开的过程中,我们很容易就能发现,在递归的过程中会有重复计
算,⽽且递归层次越深,冗余计算就会越多。

我们可以作业测试:

#include <stdio.h>
int count = 0;
int Fib(int n)
{if(n == 3)count++;//统计第3个斐波那契数被计算的次数 if(n<=2)return 1;elsereturn Fib(n-1)+Fib(n-2);
}
int main()
{int n = 0;scanf("%d", &n);int ret = Fib(n);printf("%d\n", ret); printf("\ncount = %d\n", count);return 0;
}

输出结果:
在这里插入图片描述

那我们换成迭代的方式,我们知道斐波那契数的前2个数都1,然后前2个数相加就是第3个数,那么我们从前往后,从⼩到⼤计算就⾏了。

int Fib(int n)
{int a = 1;int b = 1;int c = 1;while(n>2){c = a+b;a = b;b = c;n--;}return c;
}

迭代的⽅式去实现这个代码,效率就要⾼出很多了。
通过这个例子,可以看出,有时候,递归虽好,但是也会引⼊⼀些问题,所以我们要分辨什么时候是用递归好,什么时候是用迭代好。

小结:函数递归,博主只给你们展示了它其中的冰山一角,剩下的博主还会继续分享的。


http://www.ppmy.cn/server/153045.html

相关文章

畅捷通T+13管理员密码任意重置漏洞

复现版本 畅捷通13 漏洞复现 POST /tplus/ajaxpro/RecoverPassword,App_Web_recoverpassword.aspx.cdcab7d2.ashx?methodSetNewPwd HTTP/1.1 Host: 192.168.1.8:8080 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:124.0) Gecko/20100101 Firefox/124.0 Accept…

Mysql大数据量表分页查询性能优化

一、模拟场景 1、产品表t_product,数据量500万+ 2、未做任何优化前,cout查询时间大约4秒;LIMIT offset, count 时,offset 值较大时查询时间越久。 count查询 SELECT COUNT(*) AS total FROM t_product WHERE deleted = 0 AND tenant_id = 1 分页查询 SELECT * FROM t_…

每天40分玩转Django:Django表单集

Django表单集 一、今日学习内容概述 学习模块重要程度主要内容表单集基础⭐⭐⭐⭐⭐表单集定义、基本用法内联表单集⭐⭐⭐⭐⭐内联表单、关联数据表单集验证⭐⭐⭐⭐自定义验证、错误处理动态表单集⭐⭐⭐⭐动态添加删除表单 二、基本模型定义 # models.py from django.db…

启用Linux防火墙日志记录和分析功能

防火墙的基本功能是阻止来自可疑网络/来源的连接。它会检查所有连接的源地址、目的地址和端口,并决定是否允许或阻止流量。防火墙的每个操作都会记录为日志数据。监控和分析这些日志对于保护您的网络免受攻击至关重要。要这样做,您需要首先启用日志功能。以下是在Linux防火墙…

[创业之路-204]:《华为战略管理法-DSTE实战体系》- 5-平衡记分卡绩效管理

目录 一、平衡计分卡概述 1、平衡计分卡的基本概念 2、平衡计分卡的发展阶段 3、平衡计分卡在华为的应用 4、平衡计分卡的优缺点 五、财务&#xff08;股东&#xff09;、顾客&#xff08;用户&#xff09;、内部运营&#xff08;内部&#xff09;及学习与发展&#xff0…

微服务openfeign配置重试机制

场景&#xff1a; 1、在实际开发中&#xff0c;通过feign调用其他服务&#xff0c;如果出现read-timeout超时、或调用出现异常 2、如上问题&#xff0c;有时候可能是网络速度、网路抖动等原因导致超时异常&#xff0c;并非程序本身错误&#xff0c;所以可以配置openfeign重试…

ALPHA第四章 多态,接口,抽象类

在给出的选项中&#xff0c;错误的叙述是&#xff1a; 子类可以继承父类的构造函数 详细分析&#xff1a; 1. 子类可以继承父类的构造函数 错误的。 在 Java 中&#xff0c;子类不能继承父类的构造函数。构造函数是用来初始化对象的&#xff0c;因此构造函数是不能被继承的&a…

Linux -- 线程的优点、pthread 线程库

目录 线程的优点 pthread 线程库 前言 认识线程库 简单验证线程的独立栈空间 线程的优点 与进程之间的切换相比&#xff0c;线程之间的切换需要操作系统做的工作要少得多。 调度进程时&#xff0c;CPU 中有一个 cache&#xff08;缓存&#xff0c;提高运行效率&#xff0…