快捷導(dǎo)航

Java 方法遞歸的思路詳解

更新時(shí)間：2022年04月14日 10:23:49 作者：Killing Vibe

程序調(diào)用自身的編程技巧稱為遞歸（ recursion）。遞歸做為一種算法在程序設(shè)計(jì)語(yǔ)言中廣泛應(yīng)用。但是如果沒(méi)終止條件會(huì)造成死循環(huán)，所以遞歸代碼里要有結(jié)束自調(diào)自的條件，接下來(lái)講解一下學(xué)習(xí)遞歸的思路

前言

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

一、什么是方法遞歸

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

遞歸分為兩個(gè)子過(guò)程：

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

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

直接不好求, 可以把問(wè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

二、什么場(chǎng)景下能用遞歸

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

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

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

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

三、如何寫出遞歸代碼-重點(diǎn)

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

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

拿求5的階乘做例子：

在這里插入圖片描述

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

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

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

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

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

public static int factor(int n)

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