递归算法

经常会看到一些人,问你,“来,写一个递归算法吧”。递归算法真的那么好吗?下面是经常看到的一些题目,还有,递归算法的优缺点!
常见题:

1、计算数组{1,1,2,3,5,8,13…}第30位的值

	/**
	 * 递归方式求斐波那契
	 * @param position
	 * 第几位数字
	 * @return
	 */
	public static long Feibo1(int position){
		long result = 0;
		if (position == 1 || position == 2) {
			result = 1;
		}else {
			result = Feibo1(position-1) + Feibo1(position-2); 
		}
		return result;
	}

从此递归我们可以看出,递归就是从后面往前推获得数据,然后进行运算

但是如果第一题中的30改为40或者更大的数字,你有没有试过呢?越来越慢越来越慢……

QQ截图20150323093158

递归优点,简单明了,容易理解;缺点,就是效率低。

下面我们来换一种思路,用如下的代码:

/**
	 * 正向循环
	 * 
	 * @param position
	 *            第几位数字
	 * @return
	 */
	public static long Feibo2(int position){
		long result = 0;
		if (position ==1 || position ==2) {
			result = 1;
		}else {
			List<Integer> list = new ArrayList<>();
			list.add(1);
			list.add(1);
			for (int i = 2; i < position; i++) {
				list.add(list.get(i-1) + list.get(i-2));
			}
			result = list.get(position-1);
		}
		return result;
	}

运行的时间,瞬间缩短了。。。。。。。。。

QQ截图20150323093345

这种方法,将数据从前往后推,得出最终结果。主要是将中间的计算结果保存了起来。避免了重新计算缩短了时间。

看来我们以后还要慎用递归算法。

 

2、计算1+2+3+4+…+100的值


	/**
	 * 递归形式
	 * 求和: 1+2+3+....+n
	 * @param n 第几位
	 * @return
	 */
	public static long getSum1(int n){
		long result = 0;
		if (n == 1) {
			result = 1;
		}else {
			result = getSum1(n-1) + n;			
		}
		return result;
	}
	
	/**
	 * 数学公式
	 * 求和: 1+2+3+....+n
	 * @param n 第几位
	 */
	public static long getSum2(int n){
		long result = 0;
		result = ( n* (1 + n) )/2;
		return result;
	}

 

3、计算1-2+3-4+5-6+7…+49-50的值


	/**
	 * 计算1-2+3-4+5......+n的值
	 * @param n
	 */
	public static long getSum3(int n){
		long result = 0;
		int flag = 1;
		for (int i = 1; i <= n; i++) {
			result += flag * i;
			flag = flag*(-1);
		}
		System.err.println(result);
		return result;
	}
	
	
	/**
	 * 计算1-2+3-4+5......+n的值
	 * @param n
	 */
	public static long getSum4(int n){
		long result = 0;
		if (n % 2 == 0) {
			result = (-1) * n / 2;
		}else {
			result = (n + 1) / 2;
		}
		System.err.println(result);
		return result;
	}

实际生产环境中,要考虑算法的性能,使用可行的方案。换一种思路,性能更佳!

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注