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

1、引言
今天我们来学习递归,如果单说学习算法,递归并不能说是算法,而是一种编程的手法,为什么现在要学习这个呢?因为后面在学习其他算法时,要牵涉一些递归的调用方法,是为以后理解学习的内容做好铺垫 。
递归方法作为一种优雅的解题方法,是大多数程序员比较喜欢的编写方式之一 。递归把程序员分为三类:一种是恨它的,第二种是爱它的,最后一种是恨了一段时间之后接触之后又爱上了它 。我平时编写代码的时候可能很少用到,但我对递归的印象还是蛮喜欢的 。今天就来比较深入的学习一下递归的相关知识吧 。
2、递归
2.1.1 什么是递归
递归说白了就是用一个函数不断调用自己的过程,递归的使用可以让代码逻辑很清晰,但并没有实质性能的提升 。实质上,在有些情况下,使用循环的性能可能会更佳 。
2.1.2 递归中的两大元帅
上面介绍到递归是一个函数不断调用自己的过程,但如果没有限制结束调用的条件,就会让递归无限的循环下去 。于是编写递归函数时,必须告诉函数什么时候要停止递归调用 。这就引出了递归的两大元帅,分别为基线条件(base case)和递归条件(recursive case) 。递归条件是指让函数调用自身,而基线条件就是通知函数不要再调用自己,从而避免了无限循环 。
2.2.1 栈
使用递归必须需要了解栈的概念,栈是一种简单的数据结构,它的特点可以举一个简单的例子你就明白了 。在餐厅吃饭的时候,我们通常是在收银台进行点餐,然后点餐付款成功之后会将信息传送给后厨师傅手里,以一个先来后到的原则,厨师每次看到的信息都是最早来点餐的人的信息,而且做完之后便删掉了这个点餐信息,接着去做下一个人点的餐,而收银员每回都只在待做餐列表中添加点餐信息,而不管究竟现在有多少点餐信息 。因此这个待做餐列表就只有两种操作:存入和删除 。栈这种数据结构就是这么一个工作原理,理解了这个原理之后,我们就可以继续后面的内容了 。
2.2.2 调用栈
计算机在内部使用被称为调用栈的栈 。以一段代码解释一下计算机是如何调用栈的 。
public static void main(String[] args) {//调用方法1Greet("努力的浩浩");}//定义一个问候的方法1private static void Greet(String name){System.out.println("hello,"+name+"!");Greet2(name);System.out.println("getting ready to say bye");bye();}//定义一个问候的方法2private 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 温馨提示
使用栈虽然很方便,但是也有很大代价:如果要存储信息可能需要大量内存,每个函数调用都将占用内存,如果栈摞的很高必将


推荐阅读