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

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

什么是遞歸？

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

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

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

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

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

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

遞歸的三個條件

邊界條件

遞歸前進段

遞歸返回段

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

什么場景下適合使用遞歸

場景一

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

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

}

場景二

計算5的階乘

publicclassTest{

publicstaticvoidmain(String[]args){

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

publicstaticintf(intn){

if(1==n)

return1;

else

returnn*f(n-1);

}

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

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

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

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

總結

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

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

Java遞歸算法

一、概述

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

二、應用場景

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

使用要點：

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

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

三、示例

最簡單的遞歸演示

publicclassrecursionDemo{

publicstaticvoidmain(String[]args){

show();

privatestaticvoidshow(){

method();

privatestaticvoidmethod(){

show();

}

四、實際示例

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

代碼示例：

publicstaticvoidmain(String[]args){

toBin(6);

privatestaticvoidtoBin(intnum){

if(num0){

//取余

System.out.println(num%2);

toBin(num/2);

}

運行過程：

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

}

程序運行圖：

五、遞歸的缺點

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

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

publicstaticvoidmain(String[]args){

//1-90000000求和

intsum=getSum(90000000);

System.out.println(sum);

privatestaticintgetSum(i