快捷導(dǎo)航

Java如何利用遞歸計(jì)算出階乘

更新時(shí)間：2023年05月10日 10:05:24 作者：一一哥Sun

這篇文章主要介紹了Java如何通過遞歸計(jì)算出階乘，文中介紹了遞歸的使用方法和基本特點(diǎn)，以及相關(guān)示例代碼，對大家的學(xué)習(xí)有一定的幫助,需要的朋友可以參考下

一. 遞歸

1. 簡介

所謂的遞歸，其實(shí)是一種解決問題的方式。就是在解決具有既定規(guī)律的問題時(shí)，在方法內(nèi)部調(diào)用方法自身的一種編程方式。 即方法在運(yùn)行的過程中，不斷地自己調(diào)用自己，通過每次傳入不同的參數(shù)來解決復(fù)雜的問題。遞歸分為兩個(gè)過程，簡單地說一個(gè)是遞的過程，一個(gè)是歸的過程。

2. 使用場景

那我們什么時(shí)候使用遞歸呢？這里有幾個(gè)常見的使用場景供大家參考：

當(dāng)一個(gè)需要解決的大問題可以拆分成若干個(gè)小問題，大小問題的解決方式相同，方法中就可以自己調(diào)用自己；
可以使用循環(huán)解決的常規(guī)問題，基本都可以替換為遞歸進(jìn)行解決；
原問題和拆分后的子問題除了數(shù)據(jù)規(guī)模不同，解決思路完全相同。

3. 特點(diǎn)

遞歸具有邏輯性強(qiáng)、可讀性好，以及代碼簡潔的優(yōu)點(diǎn)。同時(shí)也有一些缺點(diǎn)，比如由于遞歸需要用到棧結(jié)構(gòu)，所以占用的空間較大，有可能會(huì)發(fā)生棧溢出。另外可能存在重復(fù)計(jì)算的問題，需要進(jìn)行一定的優(yōu)化。

4. 基本用法

如果我們要想實(shí)現(xiàn)遞歸，其實(shí)是很簡單的，直接在A方法里面調(diào)用A方法就可以了，如下所示：

methodA(){
    //遞歸調(diào)用
    methodA();
}

但是我們要注意到底該什么時(shí)候使用遞歸，且在使用遞歸時(shí)，還要設(shè)置有效的出口條件，讓調(diào)用鏈上的每個(gè)方法都可以正確返回，避免無限遞歸，不能沒完沒了。所以一個(gè)合理的遞歸，必須具備兩個(gè)條件：

一是要有邊界，即終止條件；
二是要自己調(diào)用自己。

5. 三大要素

在使用遞歸之前，我們需要明確使用遞歸時(shí)的三大要素：

明確方法想要實(shí)現(xiàn)的功能；

確定遞歸結(jié)束的條件。我們需要確定當(dāng)滿足什么條件時(shí)遞歸會(huì)結(jié)束，并把結(jié)果返回；

找出方法的等價(jià)關(guān)系式。我們可以不斷縮小參數(shù)的范圍，之后通過一些輔助的變量或操作，使原方法的結(jié)果保持不變。

6. 代碼案例

接下來通過幾個(gè)案例來給大家演示遞歸的使用。

6.1 計(jì)算階乘

大家應(yīng)該都聽過階乘的概念，那么如何通過代碼實(shí)現(xiàn)階乘的效果呢？我們先來看下圖，復(fù)習(xí)一下階乘的實(shí)現(xiàn)過程。

了解了階乘的實(shí)現(xiàn)過程之后，我們會(huì)發(fā)現(xiàn)，其實(shí)階乘每一步的實(shí)現(xiàn)過程都是類似的。所以計(jì)算某個(gè)數(shù)字階乘結(jié)果的大問題，就可以轉(zhuǎn)化為若干個(gè)小問題。比如計(jì)算5的階乘，其實(shí)就是分別單獨(dú)計(jì)算出1的階乘，2的階乘，3的階乘....每一個(gè)步驟都類似，無非就是計(jì)算的數(shù)字不同。這種情境下，我們就可以使用遞歸來解決問題，實(shí)現(xiàn)代碼如下：

/**
 * @author 一一哥Sun
 */
public class Demo07 {
    public static void main(String[] args) {
	int result = jc(5);
	System.out.println("result="+result);
    }
    //案例：求某個(gè)數(shù)的階乘，如5! = 5*4! 
    public static int jc(int num) {
	//如果數(shù)字是1，則直接返回1
	if(num == 1) {
	    return 1;
	}
	//遞歸調(diào)用，將返回的結(jié)果與num相乘
	return num*jc(num-1);
    }
}

6.2 輸出數(shù)字中每一位上的值

接下來我們再通過第二個(gè)案例來加深對遞歸的理解。這個(gè)案例是換行輸出數(shù)字中每一位上的值，如把1234的每一個(gè)數(shù)字分別輸出。

/**
 * @author 一一哥Sun
 */
public class Demo08 {
    public static void main(String[] args) {
	printNum(1234);
    }
    //換行輸出一個(gè)數(shù)字中每一位上的值，如把1234的每一個(gè)數(shù)字分別輸出。
    public static void printNum(int num) {
        //如果是0，直接終止
        if(num == 0) {
            return;
        }
        //換行輸出每一位的數(shù)字
        System.out.println(num % 10);
        //遞歸調(diào)用
        printNum(num/10);
    }
}

現(xiàn)在通過以上兩個(gè)案例，你知道遞歸是如何使用的了嗎？