文档章节

递归和非递归

Cobbage
 Cobbage
发布于 2014/12/29 22:14
字数 405
阅读 9
收藏 0

一、为什么区分下递归和非递归

递归一句话清晰

非递归后期实用

二、平时遇到的写递归和非递归

2.1只要求个结果 很直白的

//求一个数的阶乘 n*(n-1)*(n-2)...*1
--------------------------------------------------
public int factorial(int n){
		   if(1==n)return 1;
		   return n*factorial(n-1);
}

public int factorialCycle(int n){
    	int result=1;
    	for(int i=1;i<=n;i++)
    		result*=i;
    	return result;
}
--------------------------------------------------
// 1,2,3,5,8  n=(n-1)+(n-2);
  public int sumTwo(int n){
    	if(n==1||n==2)return n;
    	return sumTwo(n-1)+sumTwo(n-2);
    }
    
    public int sumTwoWhile(int n){
    	int n1=0;
    	int n2=1;
    	int temp=0;
    	for(int i=1;i<=n;i++){
    		temp=n2;
    		n2+=n1;//前两个数和
            n1=temp;    		
    	}
    	return n2;
    }

递归的结局就是找到临界点以及递归的路。临界点就是结束的那个判断条件,递归的规律

循环就是很直白的规律

2.2不直白的 要保存路径的 或者要有路径的

//这个也是求结果的
//二叉树遍历
public void preOrderTraverse(BinaryTree bt){
		if(bt!=null){
			System.out.println("当前节点值:"+bt.getNumber());
			preOrderTraverse(bt.getLeft());
			preOrderTraverse(bt.getRigth());
		}
	}
	/**
	 * 非递归先序遍历
	 */
	public void preOrderNoRecursive(BinaryTree bt){
		Stack<BinaryTree> btStack=new Stack<BinaryTree>();
		if(bt==null)return;
	while(bt!=null||!btStack.isEmpty()){	
		while(bt!=null){
			System.out.println("当前节点值:"+bt.getNumber());
			btStack.add(bt);
			bt=bt.getLeft();
		}
		
		if(!btStack.isEmpty()){
			bt=btStack.pop();
			bt=bt.getRigth();
		}
	}
//如果是求路径的 那么
递归的时候要借助堆栈,在结束判断的时候 就是一条路径
push
pop

-------------------------------
//非递归如何处理一条路径那?

三、或者要换个思路了

有些不是要做递归或者非递归,虽然也可以解,可能要别的算法。

 

 

 

 

© 著作权归作者所有

共有 人打赏支持
上一篇: 读文档啊jfinal
下一篇: Triangle
Cobbage

Cobbage

粉丝 51
博文 149
码字总数 73837
作品 1
闵行
QA/测试工程师
私信 提问
递归算法转非递归

将递归算法转换为非递归算法有两种方法,一种是直接求值,不需要回溯;另一种是不能直接求值,需要回溯。前者使用一些变量保存中间结果,称为直接转换法;后者使用栈保存中间结果,称为间接转...

u012557298
2017/12/01
0
0
递归算法转换为非递归算法的技巧

递归函数具有很好的可读性和可维护性,但是大部分情况下程序效率不如非递归函数,所以在程序设计中一般喜欢先用递归解决问题,在保证方法正确的前提下再转换为非递归函数以提高效率。 函数调...

fnqtyr45
2017/11/22
0
0
递归方法的非递归实现

递归是一种自顶向下的方法,直到方法知道如何解决最简单的问题,递归算法需要一个线性的空间开销,并且需要不断的压栈与出栈。一般来讲,非递归算法的资源开销比递归算法低。那么,我们如何实...

晨曦之光
2012/04/13
64
0
递归 (二)

原谅我好几天没写专栏,我去写放了两个月的 NOIP 题了…… 尾递归、非尾递归 首先,来两个概念:尾递归和非尾递归。 顾名思义,如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称...

BillAlen
2016/10/31
0
0
简单图像填充算法

填充算法 递归 private void fillsearch(Bitmap bmp, int x, int y, byte[,] flag,int num) { //向左 如果为1返回 如果不是1 计算当前值 如果不在范围内设为1返回 并且向下递归 if (Math.Abs...

魂祭心
2015/12/20
67
0

没有更多内容

加载失败,请刷新页面

加载更多

Hibernate SQLite方言

以下代码有参考过github上国外某位大佬的,在发文的最新稳定版Hibernate上是可用的,有时间再仔细分析一下 import org.hibernate.dialect.Dialect;import org.hibernate.dialect.function.S...

CHONGCHEN
今天
3
0
CentOS 7 MariaDB搭建主从服务器

本文编写环境为CentOS7。确保关闭SELinux,关闭防火墙或者防打开指定端口。具体信息如下 #master[root@promote ~]# cat /etc/redhat-release CentOS Linux release 7.6.1810 (Core) [r...

白豆腐徐长卿
今天
10
0
介绍python中运算符优先级

下面这个表给出Python的运算符优先级,从最低的优先级(最松散地结合)到最高的优先级(最紧密地结合)。这意味着在一个表达式中,Python会首先计算表中较下面的运算符,然后在计算列在表上部...

问题终结者
今天
3
0
Spring Boot 2.x基础教程:快速入门

简介 在您第1次接触和学习Spring框架的时候,是否因为其繁杂的配置而退却了?在你第n次使用Spring框架的时候,是否觉得一堆反复黏贴的配置有一些厌烦?那么您就不妨来试试使用Spring Boot来让...

程序猿DD
昨天
10
0
SpringSecurity认证流程源码级详解

SpringSecurity认证流程源码级详解 认证流程说明 认证结果如何在多个请求之间共享 获取认证用户信息

chendom
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部