java递归和循环

功能:求1-100的累加和

  • 方案1:使用循环
    • 方案2:使用递归
    • 递归:递归的基本思想就是“自己调用自己”,一个使用递归技术的方法将会直接或者间接的调用自己。
    • StackOverflowError:当应用程序递归太深而发生堆栈溢出时,抛出该错误。
    • 递归结构
    • 1:递归尽头:什么时候不调用自己,如果没有头,将陷入死循环
    • 常见的递归头:就是if判断
    • 2:递归体
    • 什么时候需要调用自身方法。
    • 注意:就算没有递归头,java中递归不会无限的递归下去,递归太深,堆栈内存会溢出
    • 递归次数和计算机本身的硬件有关系,以及程序本身,
    • 计算机越好,次数越多
    • 程序越简单,次数越多
    • 面试题:循环个递归区别?
    • 递归算法:
    • 优点:代码简洁、清晰,并且容易验证正确性。(如果你真的理解了算法的话,否则你更晕)
    • 缺点:它的运行需要较多次数的函数调用,如果调用层数比较深,需要增加额外的堆栈处理,比如参数传递需要压栈等操作,会对执行效率有一定影响。但是,对于某些问题,如果不使用递归,那将是极端难看的代码。
    • 循环算法:
    • 优点:速度快,结构简单。
    • 缺点:并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话,最好使用循环。
    • 递归算法 和循环算法总结
    • 一般递归调用可以处理的算法,也通过循环去解决常需要额外的低效处理 。
    • 现在的编译器在优化后,对于多次调用的函数处理会有非常好的效率优化,效率未必低于循环。

public class Demo {

	
	
	 static int i=1;
	
	public static void show(int sum){
		sum=sum+i; //业务代码1
		//递归头
		if(i==100){
			System.out.println(sum);
			return;
		}
		i++;   //业务代码2
		show(sum); //递归体
	}
	
	
	public static void main(String[] args) {
		int sum = 0;
		show(sum);
	}

}

package Test;
/*编写递归算法程序:一列数的规则如下
: 1、1、2、3、5、8、13、21、34...... 求数列的第40位数是多少*/
public class homeWork {
	public static void main(String[] args) {
		System.out.println("第40位是"+homeWork.show(40));
		
	}
	public static int show(int i){
		if(i<0){
			return 0;
		}
		else if(i>0&&i<2){
			return 1;
		}
			
		return show(i-1)+show(i-2);
	}
}

利用递归删除多级目录结构

 *  1:根目录结构是a
 *  2:判断节点是否是目录
 *  3:如果是文件,直接删除
 *  4:如果不是文件,遍历目录
 *  5:判断遍历后的每一个子节点是否为文件夹,如果不是文件夹,直接删除,如果是文件夹,继续

import java.io.File;

public class Demo {

	public static void deleteFile(File file){
		//1:判断目录是否存在
		if(file.exists()){
			//1:判断是否是文件夹
			if(file.isDirectory()){
				//2 获取文件数组
				File[] file2 = file.listFiles();
				//3 遍历文件夹
				for (File file3 : file2) {
					//4:将遍历出来的文件以及目录传入方法中
					deleteFile(file3);
				}
			}
			//直接删除文件
			file.delete();
			
		}
	}
	public static void main(String[] args) {
		//创建根目录结构的抽象路径
		File file = new File("a1");
		
		deleteFile(file);
		
		
		
		
	}
}

1,循环(loop,指的是在满足条件的情况下,重复执行同一段代码。比如,while语句。 循环则技能对应集合,列表,数组等,也能对执行代码进行操作。

2,迭代(iterate),**指的是按照某种顺序逐个访问列表中的每一项。比如,for语句。   迭代只能对应集合,列表,数组等。不能对执行代码进行迭代。

3,遍历(traversal),指的是按照一定的规则访问树形结构中的每个节点,而且每个节点都只访问一次。 遍历同迭代一样,也不能对执行代码进行遍历。

4,递归(recursion),指的是一个函数不断调用自身的行为。

(1),通俗的解释:递归就像往存钱罐里存钱,先往里边塞钱,2块,5块,10块这样的塞,叫入栈。取钱的时候,后塞进去的先取出来,这叫出栈。具体多少钱,要全部出栈才知道。

(2),递归分类:线性递归和尾递归。

递归与循环的区别

1。递归算法与迭代算法的设计思路区别在于:函数或算法是否具备收敛性,当且仅当一个算法存在预期的收敛效果时,采用递归算法才是可行的,否则,就不能使用递归算法。

当然,从理论上说,所有的递归函数都可以转换为迭代函数,反之亦然,然而代价通常都是比较高的。但从算法结构来说,递归声明的结构并不总能够转换为迭代结构,原因在于结构的引申本身属于递归的概念,用迭代的方法在设计初期根本无法实现,这就像动多态的东西并不总是可以用静多态的方法实现一样。这也是为什么在结构设计时,通常采用递归的方式而不是采用迭代的方式的原因,一个极典型的例子类似于链表,使用递归定义及其简单,但对于内存定义(数组方式)其定义及调用处理说明就变得很晦涩,尤其是在遇到环链、图、网格等问题时,使用迭代方式从描述到实现上都变得很不现实。

2。递归其实是方便了程序员难为了机器。它只要得到数学公式就能很方便的写出程序。优点就是易理解,容易编程。但递归是用栈机制实现的(c++),每深入一层,都要占去一块栈数据区域,对嵌套层数深的一些算法,递归会力不从心,空间上会以内存崩溃而告终,而且递归也带来了大量的函数调用,这也有许多额外的时间开销。所以在深度大时,它的时空性就不好了。

循环其缺点就是不容易理解,编写复杂问题时困难。优点是效率高。运行时间只因循环次数增加而增加,没什么额外开销。空间上没有什么增加。

3。局部变量占用的内存是一次性的,也就是O(1)的空间复杂度,而对于递归(不考虑尾递归优化的情况),每次函数调用都要压栈,那么空间复杂度是O(n),和递归次数呈线性关系。

4。递归程序改用循环实现的话,一般都是要自己维护一个栈的,以便状态的回溯。如果某个递归程序改用循环的时候根本就不需要维护栈,那其实这个递归程序这样写只是意义明显一些,不一定要写成递归形式。但很多递归程序就是为了利用函数自身在系统栈上的auto变量记录状态,以便回溯。

原理上讲,所有递归都是可以消除的,代价就是可能自己要维护一个栈。而且我个人认为,很多情况下用递归还是必要的,它往往能把复杂问题分解成更为简单的步骤,而且很能反映问题的本质。

首先,递归和递推又一定的相似性(当然了,不然怎么会提出这个问题?)

这两个问题都可以描述为以下形式:

f(n)=g(f(n-1),…,f(0))

这是二者的共同特点。

不同点:

1,从程序上看,递归表现为自己调用自己,递推则没有这样的形式。
2,递归是从问题的最终目标出发,逐渐将复杂问题化为简单问题,最终求得问题
是逆向的。递推是从简单问题出发,一步步的向前发展,最终求得问题。是正向的。
3,递归中,问题的n要求是计算之前就知道的,而递推可以在计算中确定,不要求计算前就知道n。
4,一般来说,递推的效率高于递归(当然是递推可以计算的情况下)

由于一切递归问题都可以转化为循环求解,因此我们可以定义广义递归:

如果转化为循环后,需要自己维护堆栈,则仍称为是递归的。

在这个定义下,有些问题适用于用递归求解,如梵塔问题有些问题适用于用递推来做,如求满足N!>M条件时最小的N。有些问题二者都可以,如给定N时的阶乘问题。至于可读性,与问题有关,不能一概而论。

递归其实就是利用系统堆栈,实现函数自身调用,或者是相互调用的过程。在通往边界的过程中,都会把单步地址保存下来,知道等出边界,再按照先进后出的进行运算,这正如我们装木桶一样,每一次都只能把东西方在最上面,而取得时候,先放进取的反而最后取出。递归的数据传送也类似。但是递归不能无限的进行下去,必须在一定条件下停止自身调用,因此它的边界值应是明确的。就向我们装木桶一样,我们不能总是无限制的往里装,必须在一定的时候把东取出来。比较简单的递归过程是阶乘函数,你可以去看一下。但是递归的运算方法,往往决定了它的效率很低,因为数据要不断的进栈出栈。这时递推便表现出它的作用了,所谓递推,就是免除了数据进出栈的过程。也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值。比如,阶乘函数中,递归的数据流动过程如下:

f(3){f(i)=f(i-1)*i}–>f(2)–>f(1)–>f(0){f(0)=1}–>f(1)–>f(2)–f(3){f(3)=6}

而递推如下:

f(0)–>f(1)–>f(2)–>f(3)

由此可见,递推的效率要高一些,在可能的情况下应尽量使用递推。但是递归作为比较基础的算法,它的作用不能忽视。所以,在把握这两种算法的时候应该特别注意。


版权声明:本文为qq_41532872原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。