您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

计算机编程必备技巧——使用递归

时间:2020-09-21 12:22:13  来源:  作者:

1、引言

今天我们来学习递归,如果单说学习算法, 递归并不能说是算法,而是一种编程的手法,为什么现在要学习这个呢?因为后面在学习其他算法时,要牵涉一些递归的调用方法,是为以后理解学习的内容做好铺垫。

递归方法作为一种优雅的解题方法,是大多数程序员比较喜欢的编写方式之一。递归把程序员分为三类:一种是恨它的,第二种是爱它的,最后一种是恨了一段时间之后接触之后又爱上了它。我平时编写代码的时候可能很少用到,但我对递归的印象还是蛮喜欢的。今天就来比较深入的学习一下递归的相关知识吧。

2、递归

2.1.1 什么是递归

递归说白了就是用一个函数不断调用自己的过程,递归的使用可以让代码逻辑很清晰,但并没有实质性能的提升。实质上,在有些情况下,使用循环的性能可能会更佳。

2.1.2 递归中的两大元帅

上面介绍到递归是一个函数不断调用自己的过程,但如果没有限制结束调用的条件,就会让递归无限的循环下去。于是编写递归函数时,必须告诉函数什么时候要停止递归调用。这就引出了递归的两大元帅,分别为基线条件(base case)和递归条件(recursive case)。递归条件是指让函数调用自身,而基线条件就是通知函数不要再调用自己,从而避免了无限循环。

2.2.1 栈

使用递归必须需要了解栈的概念,栈是一种简单的数据结构,它的特点可以举一个简单的例子你就明白了。在餐厅吃饭的时候,我们通常是在收银台进行点餐,然后点餐付款成功之后会将信息传送给后厨师傅手里,以一个先来后到的原则,厨师每次看到的信息都是最早来点餐的人的信息,而且做完之后便删掉了这个点餐信息,接着去做下一个人点的餐,而收银员每回都只在待做餐列表中添加点餐信息,而不管究竟现在有多少点餐信息。因此这个待做餐列表就只有两种操作:存入和删除。栈这种数据结构就是这么一个工作原理,理解了这个原理之后,我们就可以继续后面的内容了。

2.2.2 调用栈

计算机在内部使用被称为调用栈的栈。以一段代码解释一下计算机是如何调用栈的。

  		public static void main(String[] args) {
      //调用方法1      		Greet("努力的浩浩");
        }        //定义一个问候的方法1        private static void Greet(String name){
            System.out.println("hello,"+name+"!");
            Greet2(name);            System.out.println("getting ready to say bye");
            bye();        }        //定义一个问候的方法2        private static void Greet2(String name){
      			System.out.println("how are you,"+name+"?");
        }        //定义一个再见的方法        private static void bye(){
      			System.out.println("ok,bye!");
        }

 

下面详细介绍调用函数时内存的变化情况。

如main方法中调用了Greet("努力的浩浩");计算机会为该方法开辟一块内存空间,且存储变量name的值为"努力的浩浩",接下来执行该方法,打印出"hello,努力的浩浩!"之后,程序开始执行Greet2的方法。

当然,计算机也会为这个方法开辟一块内存空间,并且存储变量name的值为"努力的浩浩"。那么这两个方法执行的过程中,计算机就开辟了两个内存单元,于是乎计算机采用栈存储这些内存块,其中第二个内存单元位于第一个内存块的上方,打印出"how are you,努力的浩浩?"之后,从Greet2()方法中返回,此时,栈顶被弹出,于是Greet()中的变量成为了栈顶,而继续执行程序,应先打印出"getting ready to say bye"之后,再调用bye()打印出"ok,bye!"的语句。

上面这个栈由于存储了多个函数的变量,称为了调用栈。

2.2.3 递归调用栈

递归函数其实也是使用的是调用栈,我们先来定义一个递归函数,该函数完成的功能就是求数的阶乘,函数名为factorial,

如factorial(5)记作5!,其定义为5!= 5 x 4 x 3 x 2 x 1。下面是递归函数阶乘的代码!

 //定义一个递归函数阶乘
    private static int factorial(int number){
        if(number == 1)
        {            return 1;
        }        else {
            return number * factorial(number - 1);
        }    }

 

下面以一幅图来讲解递归调用栈的原理,详细分析fact(3)调用栈是如何变化的。

计算机编程必备技巧——使用递归

第一次调用


计算机编程必备技巧——使用递归

第二次调用


计算机编程必备技巧——使用递归

返回

2.3 温馨提示

使用栈虽然很方便,但是也有很大代价:如果要存储信息可能需要大量内存,每个函数调用都将占用内存,如果栈摞的很高必将

导致计算机存储大量函数调用的信息。这个时候怎么办呢?

有两种解决方案:

1、使用循环

2、使用尾递归(这个我也不懂是啥,书上就是这么写的,并非所有编程语言都支持尾递归)



Tags:递归   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
Python 3.11 pre-release已经发布。 更新日志中提到:Python 3.11 is up to 10–60% faster than Python 3.10. On average, we measured a 1.25x speedup on the standa...【详细内容】
2022-05-20  Tags: 递归  点击:(59)  评论:(0)  加入收藏
递归三要素:1、明确递归终止条件;2、给出递归终止时的处理办法;3、提取重复的逻辑,缩小问题的规模。1、1+2+3+…+nimport java.util.Scanner; public class Recursion {...【详细内容】
2022-03-18  Tags: 递归  点击:(90)  评论:(0)  加入收藏
开始切入正题之前,有必要告知大家一下,这篇文章可能有一些深度,初学者可能理解会有些吃力。我会尽量把复杂问题简单化,争取让每个阅读的童鞋们都能看得懂。希望你对element-ui,vu...【详细内容】
2022-03-16  Tags: 递归  点击:(78)  评论:(0)  加入收藏
一、问题提出问题:把m个苹果放入n个盘子中,允许有的盘子为空,共有多少种方法?注:5,1,1和1 5 1属同一种方法m,n均小于10二、算法分析设f(m,n) 为m个苹果,n个盘子的放法数目,则先对...【详细内容】
2021-11-17  Tags: 递归  点击:(171)  评论:(0)  加入收藏
对于二叉树,它的特点就是任何一个节点,左节点小于父节点、右节点大于父节点遍历二叉树有多种方式,如中序遍历、层序遍历、后序遍历,中序遍历的思路就是左-->父--->右的顺序,下面...【详细内容】
2021-11-02  Tags: 递归  点击:(114)  评论:(0)  加入收藏
正文在传统的后台管理系统里面经常会需要展示多级菜单关系,今天我们来学一下如何使用一条SQL语句展示多级菜单。现在我们有一张corpinfo单位表,里面有一个belong字段指向上级...【详细内容】
2020-12-25  Tags: 递归  点击:(277)  评论:(0)  加入收藏
1、引言今天我们来学习递归,如果单说学习算法, 递归并不能说是算法,而是一种编程的手法,为什么现在要学习这个呢?因为后面在学习其他算法时,要牵涉一些递归的调用方法,是为以后理解...【详细内容】
2020-09-21  Tags: 递归  点击:(88)  评论:(0)  加入收藏
前言递归,是一个非常重要的概念,也是面试中非常喜欢考的。因为它不但能考察一个程序员的算法功底,还能很好的考察对 时间空间复杂度 的理解和分析。本文只讲一题,也是几乎所有算...【详细内容】
2020-09-21  Tags: 递归  点击:(101)  评论:(0)  加入收藏
一、概述在本篇文章中,给大家介绍一下如何将文件进行zip压缩以及如何对zip包解压。所有这些都是使用Java提供的核心库 java.util.zip 来实现的。二、压缩文件首先我们来学...【详细内容】
2020-08-10  Tags: 递归  点击:(72)  评论:(0)  加入收藏
开始之前,首先来看一个通常我们不会以递归的形式思考的问题。假设我们想计算整数n的阶乘。n的阶乘可写作n!,其结果是1~n之间的各数之积。比如,4!=4×3×2×1。一...【详细内容】
2020-08-05  Tags: 递归  点击:(198)  评论:(0)  加入收藏
▌简易百科推荐
背景对抗是反作弊永恒的主旋律,面对对抗我们需要做到快速响应、见招拆招、在变化中发现不变的本质。在反作弊场景中,黑产必须通过文本进行信息传递或触达受害者,而文本由于其生...【详细内容】
2022-07-14  字节跳动技术团队    Tags:算法   点击:(4)  评论:(0)  加入收藏
请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(含0次)。在本题...【详细内容】
2022-07-13  做架构师不做框架师    Tags:正则表达式   点击:(6)  评论:(0)  加入收藏
高手:滑动窗口是一种比较常用的数据统计算法。简单来说,就是在一个大的数组上,定义一个固定长度的滑动窗口,然后这个窗口在数组上进行滑动。在窗口滑动的过程中,左边会出一个元素...【详细内容】
2022-07-13  跟着Mic学架构    Tags:算法   点击:(8)  评论:(0)  加入收藏
一、希尔排序介绍希尔排序这个名字,来源于它的发明者希尔,也称作“缩小增量排序”,是插入排序的一种更高效的改进版本。希尔排序是基于插入排序的以下两点性质而提出改进方法的...【详细内容】
2022-07-08  程序猿星球    Tags:希尔排序   点击:(14)  评论:(0)  加入收藏
描述为了保证第三方应用与API服务器之间通信的安全性,防止Secret Key盗用、数据篡改等恶意攻击行为,开放平台API 服务器使用签名机制,应用在调用开放平台API,需要计算出一个签...【详细内容】
2022-07-08  零一间    Tags:算法   点击:(9)  评论:(0)  加入收藏
6. 蒙特卡洛算法6.1 计算π" role="presentation" style="display: inline; font-style: normal; font-weight: normal; text-indent: 0px; text-align: left; text-trans...【详细内容】
2022-07-08  海椰人  博客园  Tags:算法   点击:(17)  评论:(0)  加入收藏
数学统计在我们的程序当中特别是数据分析当中是必不可少的一部分,本文就来介绍一下 NumPy 常见的统计函数。最大值与最小值numpy.amin()用于计算数组中的元素沿指定轴的最小...【详细内容】
2022-07-07  VT漫步    Tags:统计函数   点击:(15)  评论:(0)  加入收藏
一、基础概念1、Sorted(单调递增or单调递减)2、Bounded(存在上下界)3、Accessible by index(能够通过索引访问,数组适合,but链表不适合)二分查找是一种在每次比较之后将查找空间一...【详细内容】
2022-07-04  程序猿星球    Tags:算法   点击:(14)  评论:(0)  加入收藏
分布式系统的模型为了更容易理解分布式系统,我们先来构建一个模型。 武当派因为人口增长变成 11 个办事处分散在地图各地; 办事处之间的通信只能依靠信鸽; 一只信鸽可能无法完...【详细内容】
2022-07-01  算法的秘密    Tags:共识算法   点击:(20)  评论:(0)  加入收藏
在本课程中, 您将 详细、逐步地解释经典的精选 LeetCode 问题 ,您将了解解决技术编码面试问题的最佳方法。 这是我在准备面试时希望参加的课程。课程英文名:LeetCode in Java A...【详细内容】
2022-06-30  IT教程精选    Tags:LeetCode   点击:(19)  评论:(0)  加入收藏
站内最新
站内热门
站内头条