文档章节

编程思想之递归

自由的角马
 自由的角马
发布于 2015/01/10 13:57
字数 811
阅读 9
收藏 0


我之前写过关于递归算法的博文,但作为编程思想系列的文章不得不再对它进行进一步深入的剖析。因为它是一种简单、常用又重要的一种编程思想。

什么叫递归?

举一个通俗的例子:

有一个8俩重的苹果要你切成重量相等的若干份,每一份的重量不能大于1俩。你肯定会想到这样做:

1.第一刀先把一个苹果切成重量均等的2份A1和A2;

2.再把其中的一份A1切成重量均等的两份A11和A12, 把A2切成均等的两份A21和A22;

3.把A11切成均等的两份……

4.直到每一小份都小于等于1俩为止。

以上的例子就是递归一个模型,把一个大的事物化成若干个小的事物,每一次使用的方法都相同。

 

更为专业的定义:

程序自身调用自身的编程技巧称为递归( recursion递归有直接递归和间接递归

•直接递归:函数在执行过程中调用本身。

•间接递归:函数在执行过程中调用其它函数再经过这些函数调用本身。

递归有四个特性:

1.必须有可最终达到的终止条件,否则程序将陷入无穷循环;

2.子问题在规模上比原问题小,或更接近终止条件;

3.子问题可通过再次递归调用求解或因满足终止条件而直接求解;

4.子问题的解应能组合为整个问题的解。

 

上面的例子中也满足以上的四点性质:

(1).终止条件是每一份的重量不能大于1俩;(2).每一次切的大小都比上一次小;(3).每一次切的方式都相同,所以子问题可递归调用;(4).最终切成的每一小份也就是要求的解。

 

对上面例子的实现:

public static void sliceApple(float weight, int times){
		if (weight <= 1) {
			//System.out.println("weight:" + weight);
		} else {
			float w = weight / 2;
			System.out.println("第" + times + "次等分的重量为:" + w + "   " + w);
			times += 1;
			sliceApple(w, times);
			sliceApple(w, times);
		}
	}

	public static void main(String args[]) {
		sliceApple(8, 1);
	}

结果:

1次等分的重量为:4.0   4.0

2次等分的重量为:2.0   2.0

3次等分的重量为:1.0   1.0

3次等分的重量为:1.0   1.0

2次等分的重量为:2.0   2.0

3次等分的重量为:1.0   1.0

3次等分的重量为:1.0   1.0


递归能做什么?

将大问题分解成小问题,将复杂的问题简单化;

使程序更易于理解,增强可读性;

你会怎样使用递归?

分析问题,看看问题是否属于递归模型,能否用递归模型解决。一个问题能否用递归模型就看它是否满足递归的四个特性。

递归在调用的时候要保存调用点的信息,因此会有调用开销。在对效率有较高要求的时候,如果能用循环解决问题最好不要用递归,因为循环没有调用开销,效率会更高。

本文转载自:http://blog.csdn.net/luoweifu/article/details/42114017

自由的角马
粉丝 1
博文 269
码字总数 0
作品 0
文山
私信 提问
递归算法及经典递归例子代码实现

一、什么叫做递归? 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法; 递归函数就是直接或间接调用自身的函数,也就是自身调用自己; 二、一般什么时候使用递归? 递归时常用...

ikownyou
2017/03/24
0
0
函数式编程

函数式编程 函数式编程(Functional Programming)之前都只是听说过,没有使用过所谓的函数式编程思想。不大理解这个概念。最近弄python的时候遇到了这个概念。 函数式编程对应的是命令式编程...

王二狗子11
2018/01/07
0
0
快排 递归 非递归

我记得曾经 有一个大师说过这么一句话,大概的意思是说如果你懂得了编程,那么请你给我用非递归表达你的思想。我想非递归隐藏的东西恰恰应该是程序员应该注意的东西。因为递归的隐藏,让我们...

hyssop
2015/11/29
328
0
程序员必看的十大电影

不同的行业领域中很多时候都分享着共同的思想和理念。比如,大量的计算机编程中涉及到的概念都被运用到了电影里。有些概念出现在电影里后变得如此之 酷,甚至反过来能帮助我们程序员更好的理...

oschina
2013/10/25
34.6K
101
Scheme vs. Python

同学们一直问我,如何课程61A中是如何选择编程语言的。这个说来话长,我就不再一个一个面对面的解释了。 1. 我们需要知道的重点:选择编程语言是设计一门课程中最重要的环节。伯克利学院的宗...

ifsc01
2013/02/11
4K
9

没有更多内容

加载失败,请刷新页面

加载更多

Replugin借助“UI进程”来快速释放Dex

public static boolean preload(PluginInfo pi) { if (pi == null) { return false; } // 借助“UI进程”来快速释放Dex(见PluginFastInstallProviderProxy的说明) return PluginFastInsta......

Gemini-Lin
今天
4
0
Hibernate 5 的模块/包(modules/artifacts)

Hibernate 的功能被拆分成一系列的模块/包(modules/artifacts),其目的是为了对依赖进行独立(模块化)。 模块名称 说明 hibernate-core 这个是 Hibernate 的主要(main (core))模块。定义...

honeymoose
今天
4
0
CSS--属性

一、溢出 当内容多,元素区域小的时候,就会产生溢出效果,默认是纵向溢出 横向溢出:在内容和容器之间再套一层容器,并且内部容器要比外部容器宽 属性:overflow/overflow-x/overflow-y 取值...

wytao1995
今天
4
0
精华帖

第一章 jQuery简介 jQuery是一个JavaScript库 jQuery具备简洁的语法和跨平台的兼容性 简化了JavaScript的操作。 在页面中引入jQuery jQuery是一个JavaScript脚本库,不需要特别的安装,只需要...

流川偑
今天
7
0
语音对话英语翻译在线翻译成中文哪个方法好用

想要进行将中文翻译成英文,或者将英文翻译成中文的操作,其实有一个非常简单的工具就能够帮助完成将语音进行翻译转换的软件。 在应用市场或者百度手机助手等各大应用渠道里面就能够找到一款...

401恶户
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部