博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
编程思想之递归
阅读量:4840 次
发布时间:2019-06-11

本文共 1360 字,大约阅读时间需要 4 分钟。

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

什么叫递归?

举一个通俗的样例:

有一个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

递归能做什么?

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

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

你会如何使用递归?

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

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

关于递归的很多其他应用可阅读之前写的一篇文章:

转载于:https://www.cnblogs.com/lxjshuju/p/7116052.html

你可能感兴趣的文章
定位实现水平垂直居中的两种方法(无需计算)
查看>>
POJ 1611 The Suspects
查看>>
每日站立会议——Day5
查看>>
构建执法第二章读后感
查看>>
【收藏】win7打开word每次提示配置解决办法
查看>>
POJ1143 Number Game(DP)
查看>>
等价类划分例子中的些许添加
查看>>
《剑指offer》---斐波那契数列
查看>>
Vue自定义指令(directive)
查看>>
webservice使用注解修改WSDL内容
查看>>
SystemView 破解方法记录
查看>>
【vijos1642】班长的任务
查看>>
JavaScript入门基础(四)
查看>>
校内的hu测(10.5)
查看>>
Windows Forms高级界面组件-使用对话框
查看>>
Objective-C中的深拷贝和浅拷贝
查看>>
超实用的JQuery小技巧
查看>>
设计模式——单例模式 (C++实现)
查看>>
UML和模式应用学习笔记(6)——系统顺序图、系统操作和层
查看>>
Android -- startActivityForResult和setResult
查看>>