Java中的什么場(chǎng)景使用遞歸,如何使用遞歸

第Java中的什么場(chǎng)景使用遞歸,如何使用遞歸目錄什么是遞歸？遞歸有什么優(yōu)點(diǎn)？迭代和遞歸的區(qū)別遞歸的三個(gè)條件什么場(chǎng)景下適合使用遞歸場(chǎng)景一場(chǎng)景二總結(jié)Java遞歸算法一、概述二、應(yīng)用場(chǎng)景三、示例四、實(shí)際示例五、遞歸的缺點(diǎn)

什么是遞歸？

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

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

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

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

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

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

遞歸的三個(gè)條件

邊界條件

遞歸前進(jìn)段

遞歸返回段

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

什么場(chǎng)景下適合使用遞歸

場(chǎng)景一

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

publicvoidpackageParent(SetStringparentIdSet){

SetStringparentIdSet1=newHashSet();

for(StringparentId:parentIdSet){

MenuOrgmenuOrg=newMenuOrg();

Menumenu=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);

}

場(chǎng)景二

計(jì)算5的階乘

publicclassTest{

publicstaticvoidmain(String[]args){

System.out.println(f(5));

publicstaticintf(intn){

if(1==n)

return1;

else

returnn*f(n-1);

}

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

(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遞歸：簡(jiǎn)單說(shuō)就是函數(shù)自身直接或間接調(diào)用函數(shù)的本身。

二、應(yīng)用場(chǎng)景

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

使用要點(diǎn)：

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

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

三、示例

最簡(jiǎn)單的遞歸演示

publicclassrecursionDemo{

publicstaticvoidmain(String[]args){

show();

privatestaticvoidshow(){

method();

privatestaticvoidmethod(){

show();

}

四、實(shí)際示例

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

代碼示例：

publicstaticvoidmain(String[]args){

toBin(6);

privatestaticvoidtoBin(intnum){

if(num0){

//取余

System.out.println(num%2);

toBin(num/2);

}

運(yùn)行過(guò)程：

遞歸演示二：計(jì)算1-5，求和

publicstaticvoidmain(String[]args){

//1-5求和

intsum=getSum(5);

System.out.println(sum);

privatestaticintgetSum(intnum){

intx=9;

if(num==1){

return1;

returnnum+getSum(num-1);

}

程序運(yùn)行圖：

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

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

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

publicstaticvoidmain(String[]args){

//1-90000000求和

intsum=getSum(90000000);

System.out.println(sum);

privatestaticintgetSum(i