简单了解函数递归

函数递归

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

一 了解函数递归

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

#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.rhkb.cn/news/495118.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

QT的前景与互联网岗位发展

qt是用来干什么的 --》桌面应用开发&#xff08;做电脑的应用程序&#xff0c;面对客户端&#xff09;。 主要用于开发跨平台的应用程序和用户界面&#xff08;UI&#xff09;。它是一个全面的C库集合&#xff0c;提供了构建软件应用所需的各种工具和功能。 客户端开发的重…

重温设计模式--2、设计模式七大原则

文章目录 1、开闭原则&#xff08;Open - Closed Principle&#xff0c;OCP&#xff09;定义&#xff1a;示例&#xff1a;好处&#xff1a; 2、里氏替换原则&#xff08;Liskov Substitution Principle&#xff0c;LSP&#xff09;定义&#xff1a;示例&#xff1a;好处&#…

第十五章 C++ 数组

C 支持数组数据结构&#xff0c;它可以存储一个固定大小的相同类型元素的顺序集合。数组是用来存储一系列数据&#xff0c;但它往往被认为是一系列相同类型的变量。 数组的声明并不是声明一个个单独的变量&#xff0c;比如 number0、number1、...、number99&#xff0c;而是声…

企业数字化转型加速,现代 IT 如何用 Datadog 全面提升可观测性?

作为 Gartner 可观测平台魔力象限的领导者&#xff0c;Datadog 凭借全面的功能、直观的用户界面和强大的产品路线图赢得了全球企业的信任。 企业 IT 架构正变得日益复杂&#xff0c;从本地服务器到云端部署&#xff0c;从单体应用向微服务&#xff0c;还有容器、 Kubernetes 等…

渗透Vulnhub-DC-9靶机

本篇文章旨在为网络安全渗透测试行业靶机教学。通过阅读本文&#xff0c;读者将能够对渗透Vulnhub系列DC-6靶机有定的了解 一、信息收集阶段 DC-9靶场信息: DC-9靶场介绍&#xff1a; https://www.vulnhub.com/entry/dc-9,412/ DC-9靶场下载&#xff1a; https://download.vu…

[WASAPI]从Qt MultipleMedia来看WASAPI

[WASAPI] 从Qt MultipleMedia 来看WASAPI 最近在学习有关Windows上的音频驱动相关的知识&#xff0c;在正式开始说WASAPI之前&#xff0c;我想先说一说Qt的Multiple Media&#xff0c;为什么呢&#xff1f;因为Qt的MultipleMedia实际上是WASAPI的一层封装&#xff0c;它在是线…

Linux下编译安装Kokkos

本文记录在Linux下编译安装Kokkos的流程。 零、环境 操作系统Ubuntu 22.04.4 LTSVS Code1.92.1Git2.34.1GCC11.4.0CMake3.22.1oneAPI2024.2.1 一、安装依赖 二、编译安装 参考文献 Mills R T. PETSc/TAO Developments for Early Exascale Systems[J]. 2024.Josef R. A Stud…

HTMLCSS:惊!3D 折叠按钮

这段代码创建了一个具有 3D 效果和动画的按钮&#xff0c;按钮上有 SVG 图标和文本。按钮在鼠标悬停时会显示一个漂浮点动画&#xff0c;图标会消失并显示一个线条动画。这种效果适用于吸引用户注意并提供视觉反馈。按钮的折叠效果和背景渐变增加了页面的美观性。 演示效果 HT…

容器技术所涉及Linux内核关键技术

容器技术所涉及Linux内核关键技术 一、容器技术前世今生 1.1 1979年 — chroot 容器技术的概念可以追溯到1979年的UNIX chroot。它是一套“UNIX操作系统”系统&#xff0c;旨在将其root目录及其它子目录变更至文件系统内的新位置&#xff0c;且只接受特定进程的访问。这项功…

Git远程仓库的多人协作

目录 一.项目克隆 二.多人协作 1.创建林冲仓库 2.协作处理 3.处理冲突 三.分支推送协作 四.分支拉取协作 五.远程分支的删除 一.项目克隆 我们可以把远程项目克隆到本地形成一个本地的仓库 git clone https://github.com/txjava-teach/txjava-code.git //链接你自己的远…

Docker 部署 plumelog 最新版本 实现日志采集

1.配置plumelog.yml version: 3 services:plumelog:#此镜像是基于plumelog-3.5.3版本image: registry.cn-hangzhou.aliyuncs.com/k8s-xiyan/plumelog:3.5.3container_name: plumelogports:- "8891:8891"environment:plumelog.model: redisplumelog.queue.redis.redi…

Spring常见面试题总结

关于详细介绍&#xff0c;可以看我写的 ( Spring知识点) 这篇文章。 Spring 基础 什么是 Spring 框架? Spring 是一款开源的轻量级 Java 开发框架&#xff0c;旨在提高开发人员的开发效率以及系统的可维护性。 我们一般说 Spring 框架指的都是 Spring Framework&#xff0c…

Mac系统下 IDEA配置Maven本地仓库

1.为什么需要配置本地仓库&#xff1f; 在软件开发过程中&#xff0c;使用Maven工具进行依赖管理是常见的做法。Maven通过集中管理各种依赖库&#xff0c;能够帮助开发者在项目中轻松地引入所需的第三方库&#xff0c;并确保项目能够顺利构建和部署。然而&#xff0c;在使用Mav…

RGCL:A Review-aware Graph Contrastive Learning Framework for Recommendation

A Review-aware Graph Contrastive Learning Framework for Recommendation 解决的问题 基于评论的推荐可以自然地形成为具有来自相应用户项目评论的边特征的用户项目二分图。那么就可以利用评论感知图中独特的自监督信号来指导推荐的两个组件:用户-项目嵌入学习,用户-项目…

5、mysql的读写分离

主从复制 主从复制的含义 主从复制&#xff1a;在一个mysql的集群当中&#xff0c;至少3台&#xff0c;即主1台&#xff0c;从2台。 当有数据写入时&#xff0c;主负责写入本库&#xff0c;然后把数据同步到从服务器。 一定是在主服务器写入数据&#xff0c;从服务器的写入…

重生之我在异世界学编程之C语言:深入预处理篇(上)

大家好&#xff0c;这里是小编的博客频道 小编的博客&#xff1a;就爱学编程 很高兴在CSDN这个大家庭与大家相识&#xff0c;希望能在这里与大家共同进步&#xff0c;共同收获更好的自己&#xff01;&#xff01;&#xff01; 本文目录 引言正文一、预处理的作用与流程&#xf…

信创源代码加密的答案:信创沙箱

在信息化与工业化融合创新&#xff08;信创&#xff09;的背景下&#xff0c;企业面临着前所未有的数据安全挑战。SDC沙盒技术以其独特的隔离和保护机制&#xff0c;为信创环境提供了强有力的支持。以下是SDC沙盒在信创支持方面的优势&#xff0c;这些优势体现了其在保护企业数…

计算机网络B重修班-期末复习

[TOC] (计算机网络B重修班-期末复习&#xff09; 一、单选 &#xff08;20题&#xff0c;1分/题&#xff0c;共20分&#xff09; 二、判断 &#xff08;10题&#xff0c;1分/题&#xff0c;共10分&#xff09; 三、填空 &#xff08;10题&#xff0c;1分/题&#xff0c;共10…

结合实例从HCI层分析经典蓝牙连接和配对过程

我们知道&#xff0c;经典蓝牙BREDR的link key协商是在LMP层做的&#xff0c;那么蓝牙Host在鉴权的过程中&#xff0c;会跟BT SOC有哪些交互&#xff1a; 首次配对 在HCI Inuqiry找到想要配对的设备后&#xff0c;Host会调用HCI Create Connection命令去连接对方设备&#xf…

StartAI图生图局部重绘,让画面细节焕发新生!!

在设计的世界里&#xff0c;每一个细节都承载着我们的创意与心血。然而&#xff0c;有时我们总会遇到一些不尽如人意的画面细节&#xff0c;它们如同瑕疵般破坏了整体的和谐与美感。今天&#xff0c;我要向大家推荐一款强大的工具——StartAI的局部重绘功能&#xff0c;它正是我…