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

更新時(shí)間：2021年09月03日 11:54:27 作者：怪咖軟妹@

這篇文章主要介紹了Java中的什么場景使用遞歸,如何使用遞歸的操作，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

什么是遞歸？

程序調(diào)用自身的編程技巧叫做遞歸。

遞歸有什么優(yōu)點(diǎn)？

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

迭代和遞歸的區(qū)別

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

遞歸是將一個(gè)問題分解為若干相對小一點(diǎn)的問題，遇到遞歸出口再原路返回，因此必須保存相關(guān)的中間值，這些中間值壓入棧保存，問題規(guī)模較大時(shí)會(huì)占用大量內(nèi)存。

遞歸的三個(gè)條件

邊界條件
遞歸前進(jìn)段
遞歸返回段

當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn)；當(dāng)邊界條件滿足時(shí)，遞歸返回。

什么場景下適合使用遞歸

場景一

項(xiàng)目當(dāng)中菜單很多都是配置的，并且菜單有時(shí)候都是分好幾級(jí)的，當(dāng)我給他配置最下級(jí)的時(shí)候，那么我還得把他的上級(jí)保存起來才能用，但是我們又不確定他有幾個(gè)上級(jí)，這個(gè)時(shí)候可以采用遞歸調(diào)用。

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);
 }
}

場景二

計(jì)算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);  
    }  
}

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

(1)邊界條件：階乘，乘到最后一個(gè)數(shù)，即1的時(shí)候，返回1，程序執(zhí)行到底；

(2)遞歸前進(jìn)段：當(dāng)前的參數(shù)不等于1的時(shí)候，繼續(xù)調(diào)用自身；

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

總結(jié)

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

能用迭代的不用遞歸，遞歸調(diào)用函數(shù)，計(jì)算有重復(fù)，浪費(fèi)空間，并且遞歸太深容易造成堆棧的溢出。

Java 遞歸算法

一、概述

Java遞歸：簡單說就是函數(shù)自身直接或間接調(diào)用函數(shù)的本身。

二、應(yīng)用場景

若：一個(gè)功能在被重復(fù)使用，并每次使用時(shí)，參與運(yùn)算的結(jié)果和上一次調(diào)用有關(guān)，這時(shí)就可以使用遞歸來解決這個(gè)問題。

使用要點(diǎn)：

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

2，注意一下遞歸的次數(shù)。

三、示例

最簡單的遞歸演示

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

四、實(shí)際示例

我們都知道 6的二進(jìn)制是110,那么程序是怎么執(zhí)行的呢？

代碼示例：

 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);
        }
    }

運(yùn)行過程：

遞歸演示二：計(jì)算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);
    }

程序運(yùn)行圖：

五、遞歸的缺點(diǎn)

在使用遞歸時(shí)，一定要考慮遞歸的次數(shù)，負(fù)責(zé)很容易造成虛擬機(jī) “棧溢出”。

仍然使用上面的求和代碼，只是這次將求和基數(shù)變?yōu)?90000000，看看結(jié)果如何

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);
    }

果然就造成了虛擬機(jī)棧溢出。