首页  

递归与尾递归java实例     所属分类 java 浏览量 88
递归  尾递归

尾递归2个特点
1.在尾部调用的是函数自身(Self-called)
2.可通过优化,使得计算仅占常量栈空间(Stack Space)
       
       

斐波那契数列(Fibonacci sequence)
又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”


计算第45项
递归版本   耗时 6770 MS
尾递归版本 耗时 0 MS

result=1134903170,time1=6770
result=1134903170,time2=0


public class Fibonacci {

	public static void main(String[] args) {
		int n = 45;
		long start = System.currentTimeMillis();
		long result = fibonacci(n);
		long end = System.currentTimeMillis();
		long time = end - start;

		System.err.println("result=" + result + ",time1=" + time);

		start = System.currentTimeMillis();
		result = advanced(n, 0L, 1L);
		end = System.currentTimeMillis();
		time = end - start;

		System.err.println("result=" + result + ",time2=" + time);
	}

	// 递归版本
	private static long fibonacci(int n) {
		if (n < 0)
			return -1;
		if (n <= 1)
			return n;
		return fibonacci(n - 1) + fibonacci(n - 2);
	}

	// 尾递归版本
	private static long advanced(int n, long ret1, long ret2) {
		if (n < 0) {
			return -1;
		}
		if (n == 0) {
			return ret1;
		}
		if (n == 1) {
			return ret2;
		}
		return advanced(n - 1, ret2, ret1 + ret2);
	}

}

上一篇     下一篇
fastjson json对象 java对象 和 string 之间的转换

15条简单的职场规则

fastjson为什么这么多安全漏洞

物联网云平台简介

jdk里的泛型

springboot2单元测试