递归调用:是指在方法执行过程中出现该方法本身的调用。
分析程序从main函数开始。
递归中没有任何分支。
1. 什么是方法(函数)
java语言的方法类似于其他语言的函数,是一段来完成特定功能的代码片段,
2. 掌握方法的声明
声明格式:修饰符 返回值类型 方法名 (参数列表){
程序代码;
return 返回值就;
}
方法中的参数:
形式参数:在方法被调用时用于接收外界输入的数据。
实际参数:调用方法时实际传给方法的数据。
方法中的返回值(返回值类型:方法要返回的结果的数据类型,如一个方法没有返回值,必须给出返回值类型 void)
(返回值:方法在执行完毕后返还给调用者的数据。)
(return语句终止方法的运行并指定要返回的数据。)
3. 掌握方法的调用
java语言中使用下述形式调用方法:
对象变量名.方法名(实参列表);
实参的数目,数据类型和次序必须和所调用方法声明的形参列表匹配。
代码如下:
public class Demo11{
public static void printInfor (){
for (int i = 0; i<10 ; i++ ){
System.out.println(i);
}
}
public static int getMax(int i , int j){
int max=0;
if (i>j){
max=i;
}
else {
max=j;
}
return max;
}
public static void main (String [] args){
//System.out.println("第一次打印 ");
//printInfor();
//System.out.println("第二次打印 ");
//printInfor();
System.out.println("比较两个数输出较大的数 :");
int res = getMax(2,4);
System.out.println(res);
}
}
4. 掌握什么是方法的重载
方法的重载指的是一个类中可以定义有相同名字,但参数列表不同的多个方法,调用时,会根据不同的参数列表选择对应的方法;
参数列表是指参数的类型,个数,或顺序。
满足点认为是方法的重载:
1. 发生在同一个类中
2. 方法名相同
3. 参数列表不同(类型,大小,数量)
代码如下:
public class Demo11{
public static int getMax(int i , int j){
int max=0;
if (i>j){
max=i;
}
else {
max=j;
}
return max;
}
public static int getMax(int i , int j , int k){
int max=(i>j) ? i : j;
if(max>k){
return max;
}
else{
return k;
}
}
public static void main (String [] args){
System.out.println("比较两个数输出较大的数 :");
int res1 = getMax(2,4);
System.out.println(res1);
System.out.println("比较三个数输出较大的树 :");
int res2 = getMax(3,5,4);
System.out.println(res2);
}
}
5. 了解递归算法
1. 递归调用指的是方法执行过程中出现该方法本身的调用。
2. 递归算法关键要抓住的是:
递归出口
递推步向出口逼近
代码如下:
public class Demo12
{
public static int multip1(int n )//一般求阶乘的方法。
{
int res =1;
for (int i=1 ;i<=n ; i++ )
{
res*=i;
}
return res;
}
public static int multip2(int n)
{
if (n==1 || n==0)
{
return 1;
}
return n*multip2(n-1);
}
public static void main(String [] args)
{
System.out.println(multip1(3));
System.out.println(multip2(7));
}
}
递归算法
1.递归算法
递归在计算机科学中也称为递归算法。一些问题在分解的时候会有这样的现象:解决该问题的过程是由重复的相似子过程组成,类似这样的问题我们都可以通过递归算法进行解决。在计算机语言中,递归算法的实现靠函数的自我调用来完成,我们所见到的大多数高级编程语言都支持这样的做法。
递归算法通常有两种方式实现——普通递归和尾递归。递归方法简单的来说就是方法的内部再次调用自身,递归方法会嵌套的参与运算。这样每一个递归方法都要分配一个函数堆栈进行操作,这就是普通递归。普通递归对内存的消耗是非常大的。
另一种递归方式被称为尾递归,尾递归对普通递归进行了优化。如果使用尾递归,需要将递归方式进行特殊的设计,它需要将递归方法在return语句后进行单独调用(即尾调用)。当采用尾递归的时候,一些编程语言会进行优化,将所有嵌套的递归方法放在同一个函数堆栈中进行,效率非常快。作为一名Java程序员,如果你无法将递归方法设计成尾递归的模式也没有任何问题,因为Java并没有对尾递归进行优化 ,Java对内存的优化是依赖于回收机制。但是如果你是一名C程序员,就需要对尾递归的写法进行掌握了。
递归算法的优缺点是非常明显,算法实现简单、可读性强是递归算法的优点所在。缺点也同样明显,递归算法会占用大量内存空间,如果递归深度过大,容易发生内存相关问题。所以在递归算法中,有这样一句话:不用递归累死,滥用递归慢死。如何合理的使用递归算法,是递归使用的关键问题。
2.怎么使用递归
在设计递归算法的时候,一定要注意两点:1、设计出等价的递归公式。这一点需要我们拥有一些数学基础以及抽象概括能力,能够在复杂的运行过程中,抽象出等价的函数关系。
2、递归退出的条件。这一点尤为重要,如果递归方法没有结束条件,就如同死循环一样,让内存和CPU直接"撑爆"。常见的递归练习方法有斐波那契数列和汉诺塔移动算法。
2.1 斐波那契数列(Fibonacci sequence)
斐波那契数列是经典的递归算法应用,它是一组有规律数列:"1,1,2,3,5,8,13……",当我们要获取数列中第n位的数字时,可以总结如下公式:
当n=1或者2时,有f(n)=1,当>=3时,有f(n)=f(n-1)+f(n-2)
下面我们要设计一个方法,输出数列的前n位的信息,n通过整型参数控制。如果我们需要一个完整的数列,就需要创建一个数列容器,将数列中的每一位数字依次计算出来,并保存到容器中,最后按照顺序从容器中输出数列(如下列Java示例):
使用数组保存斐波那契数列
采用上面的做法好处非常明显,它能够记录每一位数列的值。当我们需要获取整个数列的时候,这样的方式是可取的。在一些时候,我们只想获取其中一位的数值,我们就不需要记录数列,这个时候使用递归的方式就非常方便(如下Java示例所示):
采用上述代码,可以直接获取到数列中第n位的数值。我们可以发现,使用递归的方式让代码更简洁、阅读起来更友好。下面我们创建两个测试方法,对上述两种方式进行测试:
运行结果:
2.2 汉诺塔(Hanoi)
汉诺塔是一种有趣的益智游戏,很多人在儿时都玩过这种类似的玩具(如下图所示):
汉诺塔
汉诺塔的移动规则是将所有圆盘从A柱移动到C柱上,并保持上小、下大的有序顺序摆放。在移动的过程中,也需要保持这个规则。例如上图的三层汉诺塔,我们在移动的时候有如下步骤(如下图所示):
三层汉诺塔移动步骤
如果有多个盘子,我们设盘子总数为n,我们可以分为两部分解决,一部分是上面的n-1个盘子,它们作为一个整体,另一部分是最下面的盘子n。它们移动可以分为三步:
1.将第一部分的n-1个盘子的作为一个整体,从A移动到B柱上,C柱过度。
2.接着将第n个盘子从A柱移动到C柱上。
3.再将n-1个盘子的整体从B柱移动到C柱上,A柱过度(移动规律如下图所示)。
N个盘子移动时的规律总结
用代码实现的时候,我们就可以利用递归的方式进行移动。下面代码中,我们为了观察移动过程中,各柱子上盘子的变化情况,我们用队列来模拟柱子(实现代码如下所示):
运行结果:
3.递归对循环的替代
在程序开发过程中,很多循环方法都可以使用递归来完成,例如数字的累加和阶层的计算(如下面代码所示)。
运行结果:
在上述示例代码中,我们用递归和非递归两种方式解决了累加、阶乘的循环问题。除此之外,在一些数据结构算法中,递归的使用也非常多,比如二叉树的遍历、排序等。在下面的示例中,我们使用递归的方法进行冒泡排序。
示例运行效果:
传统的冒泡排序需要借助双层循环进行排序交换。如果使用递归的方式,可以减少一层循环。在实际的排序中,我们是不推荐使用递归进行排序的,上述示例仅作为递归算法的一种思考。
递归调用:是指在方法执行过程中出现该方法本身的调用。
分析程序从main函数开始。
递归中没有任何分支。
转载于:https://www.cnblogs.com/yangyl-justdoit/p/6862057.html
在java的学习中,各位java程序员不仅要有编程的思想,也要时时刻刻积累java语言的各种算法和方法。其中,递归是java方法中的一种,想必看到这篇文章的朋友在前面已经学习掌握了java方法的相关知识点。下面这篇文章主要来学习一下java方法递归的知识。那么什么是java方法递归,递归又该如何实现呢?
Java方法递归是指在一个方法的内部调用自身的过程,以此类推就是java方法递归的理解思想,具体来讲就是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时,因为解决大问题的方法和解决小问题的方法往往是同一个方法,所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件,这样就不会产生无限递归的情况了。因此,java方法递归的两个条件就是,一通过递归调用来缩小问题规模,且新问题与原问题有着相同的形式;二存在一种简单情境,可以使递归在简单情境下退出。
我们来研究一下在不使用递归的前提下,完成1到n的求和,这个应该很简单,请看下面代码:
public class RecursionTest02 {
public static void main(String[] args) {
int n = 5;
int result = accumulate(n);
System.out.println("1到" + n + "的和是:" + result);
}
public static int accumulate(int n){
int result = 0;
for(int i = 1;i <= n; i++){
result += i;
}
return result;
}
}
运行结果如下图所示:
那么,使用递归应该怎么写呢?请看以下代码:
public class RecursionTest03 {
public static void main(String[] args) {
int n = 5;
int result = accumulate(n);
System.out.println("1到" + n + "的和是:" + result);
}
public static int accumulate(int n){
if(n == 1){
return 1;
}
return n + accumulate(n - 1);
}
}
运行结果如下图所示:
要知道java方法递归有三个要素:一定有一种可以退出程序的情况;总是在尝试将一个问题化简到更小的规模;父问题与子问题不能有重叠的部分。这是实现java方法递归的条件。
不使用java方法递归和使用方法递归的程序运行结果必然都是相同的,但是java方法递归会使代码更简单清晰,可读性更好。虽然可能java零基础的初学者不太能体会到这两个优点,但在后面的学习中,慢慢懂得在合适的程序中用合适的方法后,就会理解java方法递归的好处和作用了。