Java使用遞歸解決算法問(wèn)題的實(shí)例講解
解釋:程序調(diào)用自身的編程技巧叫做遞歸。
程序調(diào)用自身的編程技巧稱為遞歸( recursion)。遞歸做為一種算法在程序設(shè)計(jì)語(yǔ)言中廣泛應(yīng)用。 一個(gè)過(guò)程或函數(shù)在其定義或說(shuō)明中有直接或間接調(diào)用自身的一種方法,它通常把一個(gè)大型復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解,遞歸策略只需少量的程序就可描述出解題過(guò)程所需要的多次重復(fù)計(jì)算,大大地減少了程序的代碼量。遞歸的能力在于用有限的語(yǔ)句來(lái)定義對(duì)象的無(wú)限集合。
遞歸的三個(gè)條件:
1.邊界條件
2.遞歸前進(jìn)段
3.遞歸返回段
當(dāng)邊界條件不滿足時(shí),遞歸前進(jìn);當(dāng)邊界條件滿足時(shí),遞歸返回。
下面通過(guò)兩個(gè)示例程序來(lái)說(shuō)明:
1.使用Java代碼求5的階乘。(5的階乘=5*4*3*2*1)
package org.wxp.recursion; /** * 計(jì)算5的階乘(result = 5*4*3*2*1) * @author Champion.Wong */ public class Test01 { 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*(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ù)開(kāi)始乘,如果當(dāng)前參數(shù)是5,那么就是5*4,即5*(5-1),即n*(n-1)
2.使用Java代碼求數(shù)列:1,1,2,3,5,8......第40位的數(shù)
package org.wxp.recursion; /** * 求數(shù)列:1,1,2,3,5,8......第40位的數(shù) */ public class Test_02_Fibonacci { public static void main(String[] args) { System.out.println(f(6)); } public static int f(int n ) { if (1== n || 2 == n) return 1; else return f(n-1) + f(n-2); } }
3.問(wèn)題描述:求解Fibonacci數(shù)列的第10個(gè)位置的值? (斐波納契數(shù)列(Fibonacci Sequence),又稱黃金分割數(shù)列,指的是這樣一個(gè)數(shù)列:1、1、2、3、5、8、13、21、……在數(shù)學(xué)上,斐波納契數(shù)列以如下被以遞歸的方法定義:F0=0,F(xiàn)1=1,F(xiàn)n=F(n-1)+F(n-2)(n>=2,n∈N*))
程序清單:
/** *<p>Title:Java遞歸算法實(shí)例</p> *<p>Description:利用遞歸算法求解Fibonacci數(shù)列第5個(gè)數(shù)的值</p> *<p>Filename:Fibonacci.java</p> */ public class Fibonacci { /** *方法描述:求解Fibonacci數(shù)列的遞歸算法 *輸入?yún)?shù):int n *返回類型:int */ public static int fun(int n) { if(1==n || 2==n) { return 1; } else { return (fun(n-1) + fun(n-2)); } } /** *方法描述:主方法 *輸入?yún)?shù):String[] args *返回類型:void */ public static void main(String[] args) { System.out.println(fun(10)); } }
運(yùn)行結(jié)果如下所示:
相關(guān)文章
java簡(jiǎn)單實(shí)現(xiàn)用語(yǔ)音讀txt文檔方法總結(jié)
在本篇文章里小編給大家整理了關(guān)于java簡(jiǎn)單實(shí)現(xiàn)用語(yǔ)音讀txt文檔的詳細(xì)方法總結(jié),有需要的朋友們參考下。2019-06-06基于JSON和java對(duì)象的互轉(zhuǎn)方法
下面小編就為大家?guī)?lái)一篇基于JSON和java對(duì)象的互轉(zhuǎn)方法。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-09-09Springboot整合Shiro實(shí)現(xiàn)登錄與權(quán)限校驗(yàn)詳細(xì)解讀
本文給大家介紹Springboot整合Shiro的基本使用,Apache?Shiro是Java的一個(gè)安全框架,Shiro本身無(wú)法知道所持有令牌的用戶是否合法,我們將整合Shiro實(shí)現(xiàn)登錄與權(quán)限的驗(yàn)證2022-04-04PowerShell用戶認(rèn)證Function實(shí)例代碼
這篇文章主要介紹了PowerShell用戶認(rèn)證Function的資料,并附實(shí)例代碼,幫助大家學(xué)習(xí)理解,有需要的小伙伴可以參考下2016-09-09SpringBoot 多線程事務(wù)回滾的實(shí)現(xiàn)
本文是基于springboot的@Async注解開(kāi)啟多線程,并通過(guò)自定義注解和AOP實(shí)現(xiàn)的多線程事務(wù),避免繁瑣的手動(dòng)提交/回滾事務(wù),感興趣的可以了解一下2024-02-02Spring注解@Value在controller無(wú)法獲取到值的解決
這篇文章主要介紹了Spring注解@Value在controller無(wú)法獲取到值的解決,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-11-11