Java使用遞歸解決算法問題的實例講解
解釋:程序調(diào)用自身的編程技巧叫做遞歸。
程序調(diào)用自身的編程技巧稱為遞歸( recursion)。遞歸做為一種算法在程序設(shè)計語言中廣泛應(yīng)用。 一個過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法,它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解,遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計算,大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。
遞歸的三個條件:
1.邊界條件
2.遞歸前進段
3.遞歸返回段
當邊界條件不滿足時,遞歸前進;當邊界條件滿足時,遞歸返回。
下面通過兩個示例程序來說明:
1.使用Java代碼求5的階乘。(5的階乘=5*4*3*2*1)
package org.wxp.recursion; /** * 計算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); } }
此題中,按照遞歸的三個條件來分析:
(1)邊界條件:階乘,乘到最后一個數(shù),即1的時候,返回1,程序執(zhí)行到底;
(2)遞歸前進段:當前的參數(shù)不等于1的時候,繼續(xù)調(diào)用自身;
(3)遞歸返回段:從最大的數(shù)開始乘,如果當前參數(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.問題描述:求解Fibonacci數(shù)列的第10個位置的值? (斐波納契數(shù)列(Fibonacci Sequence),又稱黃金分割數(shù)列,指的是這樣一個數(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遞歸算法實例</p> *<p>Description:利用遞歸算法求解Fibonacci數(shù)列第5個數(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)); } }
運行結(jié)果如下所示:
相關(guān)文章
java簡單實現(xiàn)用語音讀txt文檔方法總結(jié)
在本篇文章里小編給大家整理了關(guān)于java簡單實現(xiàn)用語音讀txt文檔的詳細方法總結(jié),有需要的朋友們參考下。2019-06-06Springboot整合Shiro實現(xiàn)登錄與權(quán)限校驗詳細解讀
本文給大家介紹Springboot整合Shiro的基本使用,Apache?Shiro是Java的一個安全框架,Shiro本身無法知道所持有令牌的用戶是否合法,我們將整合Shiro實現(xiàn)登錄與權(quán)限的驗證2022-04-04SpringBoot 多線程事務(wù)回滾的實現(xiàn)
本文是基于springboot的@Async注解開啟多線程,并通過自定義注解和AOP實現(xiàn)的多線程事務(wù),避免繁瑣的手動提交/回滾事務(wù),感興趣的可以了解一下2024-02-02Spring注解@Value在controller無法獲取到值的解決
這篇文章主要介紹了Spring注解@Value在controller無法獲取到值的解決,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-11-11