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) ,

。。。。

依次类推。

递归调用内存泄漏的实例

看两段代码:

import java.util.ArrayList;
import java.util.List;

public class TailRecursionTest {
public static void main(String[] args) {
TailRecursionTest t = new TailRecursionTest();
for (int i = 0; i < 10000; i++)
t.a(0);
}

public void a(int j) {
j++;
List list = new ArrayList<Integer>(100000);
// 对list进行处理
}
}

没啥特殊的,仅仅是为了测试,我们将a方法调用10000次,a方法创建一个有100000个元素的list的局部变量。
第二个程序:

import java.util.ArrayList;
import java.util.List;
public class TailRecursionTest2 {
   public static void main(String[] args) {      
   TailRecursionTest2 t = new TailRecursionTest2();      
   t.a(0);   
   }   
public void a(int j) {     
   System.out.println(j);     
   j++;     
   if (j == 10000)      
      return;     
   List list = new ArrayList<integer>(100000);     // 对list进行处理     a(j);   
   } 
}</integer>

也没啥特殊的,就是将循环换成了递归,a方法做的事情没变。两个都跑一下,程序1顺利结束,程序2出问题了,啥问题?如下:

161
162
163
164
165
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.ArrayList.<init>(Unknown Source)
at TailRecursionTest2.a(TailRecursionTest2.java:17)
at TailRecursionTest2.a(TailRecursionTest2.java:20)
at TailRecursionTest2.a(TailRecursionTest2.java:20)
at TailRecursionTest2.a(TailRecursionTest2.java:20)
at TailRecursionTest2.a(TailRecursionTest2.java:20)</init>

我倒,才运行166次了,heap就满了。问题在哪呢?oh,yep,你肯定想到了,是不是重复创建list这个大集合引起的呢?它不是局部变量 吗?怎么也会溢出?是的,list是局部变量,在a的方法栈里引用着,指向heap上的大对象,更关键的问题在于,java是没有尾递归优化的,递归方法 是不会使用同一个栈帧,每一次递归调用,都将压入新的栈帧,并且这个栈帧上又new了一个list变量,引用着heap上新的一个大集合。随着栈深度的增 加, jvm里维持着一条长长的方法调用轨迹以便你能回来,在方法没有返回之前,这些list变量一直被各自的栈帧引用着,不能被GC,你说,能不OOM吗?
也许,你想到了个补救方法来挽救程序2,就是每次在处理完list后,我把它设置为null,不让栈帧继续引用着它,咱编写对gc友好的代码,这不就行了,试试:

import java.util.ArrayList;
import java.util.List;

public class TailRecursionTest2 {
    public static void main(String[] args) {       
    TailRecursionTest2 t = new TailRecursionTest2();       
    t.a(0);     
    }     
    public void a(int j) {       
    System.out.println(j);       
    j++;       
    if (j == 10000)          
      return;       
    List list = new ArrayList<integer>(100000);       // 对list进行处理       
    list = null; //gc友好  a(j);    
    } 
}</integer>

得意洋洋,我跑一下看看,这次跑到4000多次,但是:

4289
4290
4291
4292
java.lang.StackOverflowError
at sun.nio.cs.ext.DoubleByteEncoder.encodeArrayLoop(Unknown Source)
at sun.nio.cs.ext.DoubleByteEncoder.encodeLoop(Unknown Source)
at java.nio.charset.CharsetEncoder.encode(Unknown Source)
at TailRecursionTest2.a(TailRecursionTest2.java:20)
at TailRecursionTest2.a(TailRecursionTest2.java:20)
at TailRecursionTest2.a(TailRecursionTest2.java:20)

总结:在java里,递归最好咱还是别用,老老实实地while、for;就算递归了,最好递归方法不要new太大的对象,除非你能确定递归的深度不是那么大,否则OOM和堆栈溢出的阴影将笼罩着你。

Java中递归函数的使用及递归程序的缺点
文章《Java中递归函数的使用及递归程序的缺点》二维码
  • 微信打赏
  • 支付宝打赏

已有3条评论

  1. 时刻业余兼职

    支持一下啊

    2017-03-11 11:18 回复
  2. 风里芥子

    好好好

    2015-04-17 12:43 回复
  3. Adriana

    thanks for share!

    2012-02-25 21:39 回复

(必填)

(必填)

(可选)