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 回復

(必填)

(必填)

(可選)

黑龙江22选5开奖