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 &lt;= n; i++) {
x1 = func(i);
sum = sum + x1;
}

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

public static int func(int x) {
if (x &gt; 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 &lt;= 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&gt; 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&lt;=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&lt;=0)
return 0;
if(n&lt;=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和堆栈溢出的阴影将笼罩着你。

上一篇: 解决WordPress摘要尾部乱码问题下一篇: 冒泡排序算法及各种程序示例

朴人博客

Java中递归函数的使用及递归程序的缺点