Java中的什麼場景使用遞歸,如何使用遞歸

Posted on by

什麼是遞歸？

程序調用自身的編程技巧叫做遞歸。

遞歸有什麼優點？

遞歸算法：代碼簡潔、清晰，並且容易驗證正確性。在一定的程度上還能幫我們減少很多重復代碼。

迭代和遞歸的區別

迭代是逐漸逼近，用新值覆蓋舊值，直到滿足條件後結束，不保存中間值，空間利用率高。

遞歸是將一個問題分解為若幹相對小一點的問題，遇到遞歸出口再原路返回，因此必須保存相關的中間值，這些中間值壓入棧保存，問題規模較大時會占用大量內存。

遞歸的三個條件

  • 邊界條件
  • 遞歸前進段
  • 遞歸返回段

當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。

什麼場景下適合使用遞歸

場景一

項目當中菜單很多都是配置的，並且菜單有時候都是分好幾級的，當我給他配置最下級的時候，那麼我還得把他的上級保存起來才能用，但是我們又不確定他有幾個上級，這個時候可以采用遞歸調用。

public void packageParent(Set<String> parentIdSet) {
 Set<String> parentIdSet1 = new HashSet<>();
 for (String parentId : parentIdSet) {
  MenuOrg menuOrg = new MenuOrg();
  Menu menu = menuRepository.findOne(parentId);
  if (menu == null) {
   continue;
  }
  menuOrg.setMenuId(menu.getMenuId());
  menuOrg.setProType(menu.getProType());
  menuOrgRepository.save(menuOrg);
  if (menu.getParentId() != null) {
   parentIdSet1.add(menu.getParentId());
  }
 }
 //判斷parentIdSet1是否為空
 if(!CommonUtils.isCollectionBlankOrEmpty(parentIdSet1)) {
  packageParent(parentIdSet1);
 }
}

場景二

計算5的階乘

public class Test {
 public static void main(String[] args) {
  System.out.println(f(5));  
 } 
 public static int f(int n) {  
  if (1 == n)   
            return 1;  
        else  
            return n * f(n-1);  
    }  
}

此題中，按照遞歸的三個條件來分析：

(1)邊界條件：階乘，乘到最後一個數，即1的時候，返回1，程序執行到底；

(2)遞歸前進段：當前的參數不等於1的時候，繼續調用自身；

(3)遞歸返回段：從最大的數開始乘，如果當前參數是5，那麼就是54，即5(5-1)，即n*(n-1)

總結

遞歸中一定有迭代，但是迭代中不一定有遞歸，大部分可以相互轉換。

能用迭代的不用遞歸，遞歸調用函數，計算有重復，浪費空間，並且遞歸太深容易造成堆棧的溢出。

Java 遞歸算法

一、概述

Java遞歸：簡單說就是函數自身直接或間接調用函數的本身。

二、應用場景

若：一個功能在被重復使用，並每次使用時，參與運算的結果和上一次調用有關，這時就可以使用遞歸來解決這個問題。

使用要點：

1，遞歸一定明確條件。否則容易棧溢出。

2，註意一下遞歸的次數。

三、示例

最簡單的遞歸演示

public class recursionDemo {  
    public static void main(String[] args) {
        show();
    }
    private static void show() {
        method();
    }
    private static void method() {
        show();
    } 
}

四、實際示例

我們都知道 6的二進制是110,那麼程序是怎麼執行的呢？

代碼示例：

 public static void main(String[] args) {
        toBin(6);
    } 
    private static void toBin(int num) {
        if (num>0){
            //取餘
            System.out.println(num%2);
            toBin(num/2);
        }
    }

運行過程：

遞歸演示二：計算1-5，求和

public static void main(String[] args) {
        //1-5求和
        int sum = getSum(5);
        System.out.println(sum);
    } 
    private static int getSum(int num) {
        int x=9;
        if (num==1){
            return 1;
        } 
        return  num+getSum(num-1);
    }

程序運行圖：

五、遞歸的缺點

在使用遞歸時，一定要考慮遞歸的次數，負責很容易造成虛擬機 “棧溢出”。

仍然使用上面的求和代碼，隻是這次將求和基數變為 90000000，看看結果如何

public static void main(String[] args) {
        //1-90000000求和
        int sum = getSum(90000000);
        System.out.println(sum);
    }
 
    private static int getSum(int num) {
        int x=9;
        if (num==1){
            return 1;
        } 
        return  num+getSum(num-1);
    }

果然就造成瞭虛擬機棧溢出。

以上為個人經驗，希望能給大傢一個參考，也希望大傢多多支持WalkonNet。

推薦閱讀：