大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > java编程中的递归调用

java编程中的递归调用

关键词:Javajava编程中的递归调用  阅读(669) 赞(13)

[摘要]本文主要是对java编程中的递归调用的讲解,希望对大家学习java编程中的递归调用有所帮助。

1、递归函数的定义:

  答:递归函数即自调用函数,在函数体内直接或间接的调用自己,即函数的嵌套是函数本身。

  2、递归方式:递归调用有直接递归和间接递归两种方式。

  A:直接递归:在函数中出现调用函数本身。

  示例1:下面代码求斐波那契数列第n项,斐波那契数列第一和第二项是1,后面每一项是前两项之和,即1、1、2、3、5、8、13 …

  程序代码:

  public class Test {

  public static void main(String args[]) {

  int x1 = 1;

  int sum = 0;

  int n = 7;

  for (int i = 1; i <= n; i++) {

  x1 = func(i);

  sum = sum + x1;

  }

  System.out.println("sum=" + sum);

  }

  public static int func(int x) {

  if (x > 2)

  return (func(x - 1) + func(x - 2));

  else

  return 1;

  }

  }

  B:间接递归:指函数中调用了其他函数,而该其他函数有调用了本函数。

  示例2:用间接递归来计算上述斐波那契数列。

  程序代码:

  public class Test {

  public static void main(String args[]) {

  int x1 = 1;

  int sum = 0;

  int n = 7;

  for (int i = 1; i <= n; i++) {

  x1 = func1(i);

  sum = sum + x1;

  }

  System.out.println("sum=" + sum);

  }

  public static int func1(int a){

  int b;

  b=func2(a);

  return b;

  }

  public static int func2(int b) {

  if (b> 2)

  return (func1(b - 1) + func1(b - 2));

  else

  return 1;

  }

  }

 

  3、为什么要用递归函数?递归函数的缺点是什么?

  答:递归的目的是简化程序设计,使程序易读。

  示例3:下面不用递归函数继续来计算上述斐波那契数列。

  程序代码:

  public class Test {

  public static void main(String args[]) {

  int n=7;

  int a=1, b=1, temp;

  int sum=2;

  for(int i=3; i<=n; i++){

  temp=a+b; a=b; b=temp;

  sum=sum+temp;

  }

  System.out.println("sum=" + sum);

  }

  }

  从上面例子我们可以发现虽然非递归函数效率高,但较难编程,可读性较差。递归函数的缺点是增加了系统开销,也就是说,每递归一次,栈内存就多占用一截。

  4、递归的条件:

  答:需有完成任务的语句,需满足递归的要求(减小而不是发散)。

  5、递归进阶:

  示例4:

  编程求解:若一头小母牛,从出生起第四个年头开始每年生一头母牛,按次规律,第n年时有多少头母牛?

  程序代码:

  public class Test3 {

  public static void main(String args[]) {

  int n=10; //要查看的年数

  System.out.println("共有"+cattle(n)+"头小母牛!");

  }

  public static int cattle(int n){

  if(n<=0)

  return 0;

  if(n<=3)

  return 1;

  return cattle(n-1)+ cattle(n-3);//此处是递归要好好理解。

  }

  }

  规律:此类问题的递归函数为:

  如果要求的是从出生起第四个年头,则递归函数为cattle(n-1)+ cattle(n-3),

  如果要求的是从出生起第五个年头,则递归函数为cattle(n-1)+ cattle(n-4),

  …

  依次类推。



相关评论