java面试题:递归方法

Posted on 2010-05-22 13:40 java小爬虫 阅读(2952) 评论(2)  编辑  收藏
今天参加了一场java笔试,考了斐波那契数列。以前也见过考阶乘的。今天顺手把它写下来。

public class Recursion {

 public static long factorial(int i) {
  if (i < 0)
   return -1;
  else if (i == 0 || i == 1)
   return 1;
  else
   return i * factorial(i - 1);
 }

 public static int sum(int i) {
  if (i == 0)
   return 0;
  else
   return i + sum(i - 1);
 }

 public static int fibonacci(int i) {
  if (i == 0 || i == 1)
   return 1;
  else
   return fibonacci(i - 1) + fibonacci(i - 2);
 }

 public static void main(String[] args) {
  for (int i = 0; i < 5; i++) {
   System.out.println(i + "!= " + factorial(i));
   System.out.println("sum(" + i + "!) = " + sum(i));
   System.out.println("fibonacci(" + i + ")= " + fibonacci(i));
   System.out.println("=========================");
  }
 }

}

Feedback

# re: java面试题:递归方法[未登录]  回复  更多评论   

2010-05-23 01:23 by hunter
fibonacci这个函数算法效率有点低呀,有很多重复运算,当输入值很大的时候就很慢咯~

# re: java面试题:递归方法  回复  更多评论   

2010-05-23 11:02 by java小爬虫
@hunter

你说的对,递归调用次数太多的话,有java栈溢出的问题。即使没有栈溢出的问题,递归次数多效率也是问题!

下面是一种没有用递归的方法:

public static void fibonacci(int m) {
long x = 1, y = 1;
System.out.println("fibonacci(1) = "+x);
for (int i = 1; i <= m; i++) {
System.out.println("fibonacci("+(i+1)+") = "+y);
y = x + y;
x = y - x;
}

}

只有注册用户登录后才能发表评论。


网站导航: