前言

今天給老鐵們回顧一下遞歸的思路以及方法，也是給自己的一個歸納總結(jié)。

一、什么是方法遞歸

所謂的方法遞歸，就是在一個方法（函數(shù)）執(zhí)行的內(nèi)部，自己調(diào)用了自己的過程，稱之為 “遞歸” 。

遞歸分為兩個子過程：

• 遞過程：函數(shù)不斷地調(diào)用自身，直到走到函數(shù)的終止條件，第一階段結(jié)束。
• 歸過程：函數(shù)不斷地返回的過程。

例如, 我們求 N! 起始條件: N = 1 的時候, N! 為 1. 這個起始條件相當于遞歸的結(jié)束條件. 遞歸公式: 求 N! ,

直接不好求, 可以把問題轉(zhuǎn)換成 N! => N * (N-1)!

示例：遞歸求N的階乘

public static void main(String[] args) {
    int n = 5;
    int ret = factor(n);
    System.out.println("ret = " + ret);
}
public static int factor(int n) {
    if (n == 1) {
        return 1;
   }
    return n * factor(n - 1); // factor 調(diào)用函數(shù)自身
}
// 執(zhí)行結(jié)果
ret = 120

二、什么場景下能用遞歸

a.一個大問題（這個方法的功能）可以拆分成若干個子問題的解.

b.拆分后的子問題和原問題除了數(shù)據(jù)規(guī)模不同，解決思路完全相同.

c.必須存在遞歸的終止條件（不會無限拆分下去，一定能走到底~）.

（看不懂先看下面(●ˇ∀ˇ●)）

三、如何寫出遞歸代碼-重點

• 先考慮這個函數(shù)的終止條件

比如上面的栗子：求N的階乘。

拿求5的階乘做例子：

我們把大問題（5的階乘）一直拆分到1的時候，問題無法繼續(xù)拆分下去了，這個子問題就是這個遞歸的最終條件。

所以我們寫代碼的時候，可以先把最終條件寫上：

if (n == 1) {
        return 1;
   }

• 假設(shè)這個函數(shù)已經(jīng)寫好了（注意這個方法的語義）

在寫遞歸函數(shù)的時候，千萬不要糾結(jié)這個函數(shù)內(nèi)部是如何實現(xiàn)的，而是要注意這個函數(shù)有什么功能（假設(shè)這個函數(shù)別人已經(jīng)寫好了），我們把它當作一個黑盒子，你只是去調(diào)用這個函數(shù)罷了。

public static int factor(int n)

比如這個函數(shù)只能傳入一個n，目前我們只能知道這個n是多少，而n的階乘等于n* [(n-1)!]，但是我們并不知道n-1的階乘是多少，那么就調(diào)用這個別人寫好的“黑盒子”。這個黑盒子的功能可以實現(xiàn)某個數(shù)的階乘。

n * factor(n - 1) // n*黑盒子

說白了就是，把這個factor函數(shù)當作別人已經(jīng)寫好了，你只需要關(guān)注如何去調(diào)用這個方法去輔助你解決問題就可以了！

總結(jié)

寫出遞歸其實=終止條件+利用黑盒子去解決剩下的問題，注意傳入的參數(shù)就可以很快把遞歸代碼寫出來(●ˇ∀ˇ●)。

到此這篇關(guān)于Java 方法遞歸的思路詳解的文章就介紹到這了,更多相關(guān)Java 遞歸內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論