Java數(shù)據(jù)結(jié)構(gòu)——遞歸

2.3 遞歸

概述

定義

計(jì)算機(jī)科學(xué)中，遞歸是一種解決計(jì)算問題的方法锌订，其中解決方案取決于同一類問題的更小子集

In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.

比如單鏈表遞歸遍歷的例子：

void f(Node node) {
    if(node == null) {
        return;
    }
    println("before:" + node.value)
    f(node.next);
    println("after:" + node.value)
}

說明：

自己調(diào)用自己竹握，如果說每個(gè)函數(shù)對(duì)應(yīng)著一種解決方案，自己調(diào)用自己意味著解決方案是一樣的（有規(guī)律的）
每次調(diào)用辆飘，函數(shù)處理的數(shù)據(jù)會(huì)較上次縮減（子集）啦辐，而且最后會(huì)縮減至無需繼續(xù)遞歸
內(nèi)層函數(shù)調(diào)用（子集處理）完成，外層函數(shù)才能算調(diào)用完成

原理

假設(shè)鏈表中有 3 個(gè)節(jié)點(diǎn)蜈项，value 分別為 1芹关，2，3紧卒，以上代碼的執(zhí)行流程就類似于下面的偽碼

// 1 -> 2 -> 3 -> null  f(1)

void f(Node node = 1) {
    println("before:" + node.value) // 1
    void f(Node node = 2) {
        println("before:" + node.value) // 2
        void f(Node node = 3) {
            println("before:" + node.value) // 3
            void f(Node node = null) {
                if(node == null) {
                    return;
                }
            }
            println("after:" + node.value) // 3
        }
        println("after:" + node.value) // 2
    }
    println("after:" + node.value) // 1
}

思路

確定能否使用遞歸求解
推導(dǎo)出遞推關(guān)系侥衬，即父問題與子問題的關(guān)系，以及遞歸的結(jié)束條件

例如之前遍歷鏈表的遞推關(guān)系為
$f(n) = \begin{cases} 停止& n = null \\ f(n.next) & n \neq null \end{cases}$

深入到最里層叫做遞
從最里層出來叫做歸
在遞的過程中跑芳，外層函數(shù)內(nèi)的局部變量（以及方法參數(shù)）并未消失轴总，歸的時(shí)候還可以用到

單路遞歸 Single Recursion

E01. 階乘

用遞歸方法求階乘

階乘的定義 $n!= 1?2?3?(n-2)?(n-1)?n$ ，其中 $n$ 為自然數(shù)博个，當(dāng)然 $0! = 1$
遞推關(guān)系

$f(n) = \begin{cases} 1 & n = 1\\ n * f(n-1) & n > 1 \end{cases}$

代碼

private static int f(int n) {
    if (n == 1) {
        return 1;
    }
    return n * f(n - 1);
}

拆解偽碼如下怀樟，假設(shè) n 初始值為 3

f(int n = 3) { // 解決不了,遞
    return 3 * f(int n = 2) { // 解決不了,繼續(xù)遞
        return 2 * f(int n = 1) {
            if (n == 1) { // 可以解決, 開始?xì)w
                return 1;
            }
        }
    }
}

E02. 反向打印字符串

用遞歸反向打印字符串，n 為字符在整個(gè)字符串 str 中的索引位置

遞：n 從 0 開始盆佣，每次 n + 1往堡，一直遞到 n == str.length() - 1
歸：從 n == str.length() 開始?xì)w，從歸打印罪塔，自然是逆序的

遞推關(guān)系
$f(n) = \begin{cases} 停止 & n = str.length() \\ f(n+1) & 0 \leq n \leq str.length() - 1 \end{cases}$
代碼為

public static void reversePrint(String str, int index) {
    if (index == str.length()) {
        return;
    }
    reversePrint(str, index + 1);
    System.out.println(str.charAt(index));
}

拆解偽碼如下投蝉，假設(shè)字符串為 "abc"

void reversePrint(String str, int index = 0) {
    void reversePrint(String str, int index = 1) {
        void reversePrint(String str, int index = 2) {
            void reversePrint(String str, int index = 3) { 
                if (index == str.length()) {
                    return; // 開始?xì)w
                }
            }
            System.out.println(str.charAt(index)); // 打印 c
        }
        System.out.println(str.charAt(index)); // 打印 b
    }
    System.out.println(str.charAt(index)); // 打印 a
}

多路遞歸 Multi Recursion

E01. 斐波那契數(shù)列

之前的例子是每個(gè)遞歸函數(shù)只包含一個(gè)自身的調(diào)用，這稱之為 single recursion
如果每個(gè)遞歸函數(shù)例包含多個(gè)自身調(diào)用征堪，稱之為 multi recursion

遞推關(guān)系
$f(n) = \begin{cases} 0 & n=0 \\ 1 & n=1 \\ f(n-1) + f(n-2) & n>1 \end{cases}$

下面的表格列出了數(shù)列的前幾項(xiàng)

F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13
0	1	1	2	3	5	8	13	21	34	55	89	144	233

實(shí)現(xiàn)

public static int f(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    return f(n - 1) + f(n - 2);
}

執(zhí)行流程

2.gif

綠色代表正在執(zhí)行（對(duì)應(yīng)遞）瘩缆，灰色代表執(zhí)行結(jié)束（對(duì)應(yīng)歸）
遞不到頭，不能歸佃蚜，對(duì)應(yīng)著深度優(yōu)先搜索

時(shí)間復(fù)雜度

遞歸的次數(shù)也符合斐波那契規(guī)律庸娱， $2 * f(n+1)-1$
時(shí)間復(fù)雜度推導(dǎo)過程
- 斐波那契通項(xiàng)公式 $f(n) = \frac{1}{\sqrt{5}}*({\frac{1+\sqrt{5}}{2}}^n - {\frac{1-\sqrt{5}}{2}}^n)$
- 簡(jiǎn)化為： $f(n) = \frac{1}{2.236}*({1.618}^n - {(-0.618)}^n)$
- 帶入遞歸次數(shù)公式 $2*\frac{1}{2.236}*({1.618}^{n+1} - {(-0.618)}^{n+1})-1$
- 時(shí)間復(fù)雜度為 $\Theta(1.618^n)$

更多 Fibonacci 參考[^8][9][^10]

以上時(shí)間復(fù)雜度分析，未考慮大數(shù)相加的因素

變體1 - 兔子問題[^8]

image.png

第一個(gè)月谐算，有一對(duì)未成熟的兔子（黑色熟尉，注意圖中個(gè)頭較小）
第二個(gè)月洲脂，它們成熟
第三個(gè)月斤儿，它們能產(chǎn)下一對(duì)新的小兔子（藍(lán)色）
所有兔子遵循相同規(guī)律剧包，求第 $n$ 個(gè)月的兔子數(shù)

分析

兔子問題如何與斐波那契聯(lián)系起來呢？設(shè)第 n 個(gè)月兔子數(shù)為 $f(n)$

$f(n)$ = 上個(gè)月兔子數(shù) + 新生的小兔子數(shù)
而【新生的小兔子數(shù)】實(shí)際就是【上個(gè)月成熟的兔子數(shù)】
因?yàn)樾枰粋€(gè)月兔子就成熟往果，所以【上個(gè)月成熟的兔子數(shù)】也就是【上上個(gè)月的兔子數(shù)】
上個(gè)月兔子數(shù)疆液，即 $f(n-1)$
上上個(gè)月的兔子數(shù)，即 $f(n-2)$

因此本質(zhì)還是斐波那契數(shù)列陕贮，只是從其第一項(xiàng)開始

變體2 - 青蛙爬樓梯

樓梯有 $n$ 階
青蛙要爬到樓頂堕油，可以一次跳一階，也可以一次跳兩階
只能向上跳肮之，問有多少種跳法

分析

n	跳法	規(guī)律
1	(1)	暫時(shí)看不出
2	(1,1) (2)	暫時(shí)看不出
3	(1,1,1) (1,2) (2,1)	暫時(shí)看不出
4	(1,1,1,1) (1,2,1) (2,1,1)<br />(1,1,2) (2,2)	最后一跳掉缺，跳一個(gè)臺(tái)階的，基于f(3)<br />最后一跳戈擒，跳兩個(gè)臺(tái)階的眶明，基于f(2)
5	...	...

因此本質(zhì)上還是斐波那契數(shù)列，只是從其第二項(xiàng)開始
對(duì)應(yīng) leetcode 題目 70. 爬樓梯 - 力扣（LeetCode）

遞歸優(yōu)化-記憶法

上述代碼存在很多重復(fù)的計(jì)算峦甩，例如求 $f(5)$ 遞歸分解過程

image.png

可以看到（顏色相同的是重復(fù)的）：

$f(3)$ 重復(fù)了 2 次
$f(2)$ 重復(fù)了 3 次
$f(1)$ 重復(fù)了 5 次
$f(0)$ 重復(fù)了 3 次

隨著 $n$ 的增大赘来，重復(fù)次數(shù)非诚衷可觀凯傲，如何優(yōu)化呢？

Memoization 記憶法（也稱備忘錄）是一種優(yōu)化技術(shù)嗦篱，通過存儲(chǔ)函數(shù)調(diào)用結(jié)果（通常比較昂貴）冰单，當(dāng)再次出現(xiàn)相同的輸入（子問題）時(shí)，就能實(shí)現(xiàn)加速效果灸促，改進(jìn)后的代碼

public static void main(String[] args) {
    int n = 13;
    int[] cache = new int[n + 1];
    Arrays.fill(cache, -1);
    cache[0] = 0;
    cache[1] = 1;
    System.out.println(f(cache, n));
}

public static int f(int[] cache, int n) {
    if (cache[n] != -1) {
        return cache[n];
    }

    cache[n] = f(cache, n - 1) + f(cache, n - 2);
    return cache[n];
}

優(yōu)化后的圖示诫欠，只要結(jié)果被緩存，就不會(huì)執(zhí)行其子問題

image.png

改進(jìn)后的時(shí)間復(fù)雜度為 $O(n)$
請(qǐng)自行驗(yàn)證改進(jìn)后的效果
請(qǐng)自行分析改進(jìn)后的空間復(fù)雜度

注意

記憶法是動(dòng)態(tài)規(guī)劃的一種情況浴栽，強(qiáng)調(diào)的是自頂向下的解決

記憶法的本質(zhì)是空間換時(shí)間

遞歸優(yōu)化-尾遞歸

爆棧

用遞歸做 $n + (n-1) + (n-2) ... + 1$

public static long sum(long n) {
    if (n == 1) {
        return 1;
    }
    return n + sum(n - 1);
}

在我的機(jī)器上 $n = 12000$ 時(shí)荒叼，爆棧了

Exception in thread "main" java.lang.StackOverflowError
    at Test.sum(Test.java:10)
    at Test.sum(Test.java:10)
    at Test.sum(Test.java:10)
    at Test.sum(Test.java:10)
    at Test.sum(Test.java:10)
    ...

為什么呢？

每次方法調(diào)用是需要消耗一定的棧內(nèi)存的典鸡，這些內(nèi)存用來存儲(chǔ)方法參數(shù)被廓、方法內(nèi)局部變量、返回地址等等
方法調(diào)用占用的內(nèi)存需要等到方法結(jié)束時(shí)才會(huì)釋放
而遞歸調(diào)用我們之前講過萝玷，不到最深不會(huì)回頭嫁乘，最內(nèi)層方法沒完成之前，外層方法都結(jié)束不了
- 例如球碉， $sum(3)$ 這個(gè)方法內(nèi)有個(gè)需要執(zhí)行 $3 + sum(2)$ 蜓斧， $sum(2)$ 沒返回前，加號(hào)前面的 $3$ 不能釋放
- 看下面?zhèn)未a

long sum(long n = 3) {
    return 3 + long sum(long n = 2) {
        return 2 + long sum(long n = 1) {
            return 1;
        }
    }
}

尾調(diào)用

如果函數(shù)的最后一步是調(diào)用一個(gè)函數(shù)睁冬，那么稱為尾調(diào)用挎春，例如

function a() {
    return b()
}

下面三段代碼不能叫做尾調(diào)用

function a() {
    const c = b()
    return c
}

因?yàn)樽詈笠徊讲⒎钦{(diào)用函數(shù)

function a() {
    return b() + 1
}

最后一步執(zhí)行的是加法

function a(x) {
    return b() + x
}

最后一步執(zhí)行的是加法

一些語言[^11]的編譯器能夠?qū)ξ舱{(diào)用做優(yōu)化，例如

function a() {
    // 做前面的事
    return b() 
}

function b() {
    // 做前面的事
    return c()
}

function c() {
    return 1000
}

a()

沒優(yōu)化之前的偽碼

function a() {
    return function b() {
        return function c() {
            return 1000
        }
    }
}

優(yōu)化后偽碼如下

a()
b()
c()

為何尾遞歸才能優(yōu)化？

調(diào)用 a 時(shí)

a 返回時(shí)發(fā)現(xiàn)：沒什么可留給 b 的直奋，將來返回的結(jié)果 b 提供就可以了狼荞，用不著我 a 了，我的內(nèi)存就可以釋放

調(diào)用 b 時(shí)

b 返回時(shí)發(fā)現(xiàn)：沒什么可留給 c 的帮碰，將來返回的結(jié)果 c 提供就可以了相味，用不著我 b 了，我的內(nèi)存就可以釋放

如果調(diào)用 a 時(shí)

不是尾調(diào)用殉挽，例如 return b() + 1丰涉，那么 a 就不能提前結(jié)束，因?yàn)樗€得利用 b 的結(jié)果做加法

尾遞歸

尾遞歸是尾調(diào)用的一種特例斯碌，也就是最后一步執(zhí)行的是同一個(gè)函數(shù)

尾遞歸避免爆棧

安裝 Scala

image.png

Scala 入門

object Main {
  def main(args: Array[String]): Unit = {
    println("Hello Scala")
  }
}

Scala 是 java 的近親一死，java 中的類都可以拿來重用
類型是放在變量后面的
Unit 表示無返回值，類似于 void
不需要以分號(hào)作為結(jié)尾傻唾，當(dāng)然加上也對(duì)

還是先寫一個(gè)會(huì)爆棧的函數(shù)

def sum(n: Long): Long = {
    if (n == 1) {
        return 1
    }
    return n + sum(n - 1)
}

Scala 最后一行代碼若作為返回值投慈，可以省略 return

不出所料，在 $n = 11000$ 時(shí)冠骄，還是出了異常

println(sum(11000))

Exception in thread "main" java.lang.StackOverflowError
    at Main$.sum(Main.scala:25)
    at Main$.sum(Main.scala:25)
    at Main$.sum(Main.scala:25)
    at Main$.sum(Main.scala:25)
    ...

這是因?yàn)橐陨洗a伪煤，還不是尾調(diào)用，要想成為尾調(diào)用凛辣，那么：

最后一行代碼抱既，必須是一次函數(shù)調(diào)用
內(nèi)層函數(shù)必須擺脫與外層函數(shù)的關(guān)系，內(nèi)層函數(shù)執(zhí)行后不依賴于外層的變量或常量

def sum(n: Long): Long = {
    if (n == 1) {
        return 1
    }
    return n + sum(n - 1)  // 依賴于外層函數(shù)的 n 變量
}

如何讓它執(zhí)行后就擺脫對(duì) n 的依賴呢扁誓？

不能等遞歸回來再做加法防泵，那樣就必須保留外層的 n
把 n 當(dāng)做內(nèi)層函數(shù)的一個(gè)參數(shù)傳進(jìn)去，這時(shí) n 就屬于內(nèi)層函數(shù)了
傳參時(shí)就完成累加, 不必等回來時(shí)累加

sum(n - 1, n + 累加器)

改寫后代碼如下

@tailrec
def sum(n: Long, accumulator: Long): Long = {
    if (n == 1) {
        return 1 + accumulator
    } 
    return sum(n - 1, n + accumulator)
}

accumulator 作為累加器
@tailrec 注解是 scala 提供的蝗敢，用來檢查方法是否符合尾遞歸
這回 sum(10000000, 0) 也沒有問題捷泞，打印 50000005000000

執(zhí)行流程如下，以偽碼表示 $sum(4, 0)$

// 首次調(diào)用
def sum(n = 4, accumulator = 0): Long = {
    return sum(4 - 1, 4 + accumulator)
}

// 接下來調(diào)用內(nèi)層 sum, 傳參時(shí)就完成了累加, 不必等回來時(shí)累加寿谴，當(dāng)內(nèi)層 sum 調(diào)用后锁右，外層 sum 空間沒必要保留
def sum(n = 3, accumulator = 4): Long = {
    return sum(3 - 1, 3 + accumulator)
}

// 繼續(xù)調(diào)用內(nèi)層 sum
def sum(n = 2, accumulator = 7): Long = {
    return sum(2 - 1, 2 + accumulator)
}

// 繼續(xù)調(diào)用內(nèi)層 sum, 這是最后的 sum 調(diào)用完就返回最后結(jié)果 10, 前面所有其它 sum 的空間早已釋放
def sum(n = 1, accumulator = 9): Long = {
    if (1 == 1) {
        return 1 + accumulator
    }
}

本質(zhì)上，尾遞歸優(yōu)化是將函數(shù)的遞歸調(diào)用拭卿，變成了函數(shù)的循環(huán)調(diào)用

改循環(huán)避免爆棧

public static void main(String[] args) {
    long n = 100000000;
    long sum = 0;
    for (long i = n; i >= 1; i--) {
        sum += i;
    }
    System.out.println(sum);
}

遞歸時(shí)間復(fù)雜度-Master theorem[^14]

若有遞歸式
$T(n) = aT(\frac{n}骡湖) + f(n)$
其中

$T(n)$ 是問題的運(yùn)行時(shí)間， $n$ 是數(shù)據(jù)規(guī)模
$a$ 是子問題個(gè)數(shù)
$T(\frac{n}峻厚)$ 是子問題運(yùn)行時(shí)間响蕴，每個(gè)子問題被拆成原問題數(shù)據(jù)規(guī)模的 $\frac{n}$
$f(n)$ 是除遞歸外執(zhí)行的計(jì)算

令 $x = \log_惠桃{a}$ 浦夷，即 $x = \log_{子問題縮小倍數(shù)}{子問題個(gè)數(shù)}$

那么
$T(n) = \begin{cases} \Theta(n^x) & f(n) = O(n^c) 并且 c \lt x\\ \Theta(n^x\log{n}) & f(n) = \Theta(n^x)\\ \Theta(n^c) & f(n) = \Omega(n^c) 并且 c \gt x \end{cases}$

例1

$T(n) = 2T(\frac{n}{2}) + n^4$

此時(shí) $x = 1 < 4$ 辖试，由后者決定整個(gè)時(shí)間復(fù)雜度 $\Theta(n^4)$
如果覺得對(duì)數(shù)不好算，可以換為求【 $b$ 的幾次方能等于 $a$ 】

例2

$T(n) = T(\frac{7n}{10}) + n$

$a=1, b=\frac{10}{7}, x=0, c=1$
此時(shí) $x = 0 < 1$ 劈狐，由后者決定整個(gè)時(shí)間復(fù)雜度 $\Theta(n)$

例3

$T(n) = 16T(\frac{n}{4}) + n^2$

$a=16, b=4, x=2, c=2$
此時(shí) $x=2 = c$ 罐孝，時(shí)間復(fù)雜度 $\Theta(n^2 \log{n})$

例4

$T(n)=7T(\frac{n}{3}) + n^2$

$a=7, b=3, x=1.?, c=2$
此時(shí) $x = \log_{3}{7} < 2$ ，由后者決定整個(gè)時(shí)間復(fù)雜度 $\Theta(n^2)$

例5

$T(n) = 7T(\frac{n}{2}) + n^2$

$a=7, b=2, x=2.?, c=2$
此時(shí) $x = log_2{7} > 2$ 肥缔，由前者決定整個(gè)時(shí)間復(fù)雜度 $\Theta(n^{\log_2{7}})$

例6

$T(n) = 2T(\frac{n}{4}) + \sqrt{n}$

$a=2, b=4, x = 0.5, c=0.5$
此時(shí) $x = 0.5 = c$ 莲兢，時(shí)間復(fù)雜度 $\Theta(\sqrt{n}\ \log{n})$

例7. 二分查找遞歸

int f(int[] a, int target, int i, int j) {
    if (i > j) {
        return -1;
    }
    int m = (i + j) >>> 1;
    if (target < a[m]) {
        return f(a, target, i, m - 1);
    } else if (a[m] < target) {
        return f(a, target, m + 1, j);
    } else {
        return m;
    }
}

子問題個(gè)數(shù) $a = 1$
子問題數(shù)據(jù)規(guī)模縮小倍數(shù) $b = 2$
除遞歸外執(zhí)行的計(jì)算是常數(shù)級(jí) $c=0$

$T(n) = T(\frac{n}{2}) + n^0$

此時(shí) $x=0 = c$ 续膳，時(shí)間復(fù)雜度 $\Theta(\log{n})$

例8. 歸并排序遞歸

void split(B[], i, j, A[])
{
    if (j - i <= 1)                    
        return;                                
    m = (i + j) / 2;             
    
    // 遞歸
    split(A, i, m, B);  
    split(A, m, j, B); 
    
    // 合并
    merge(B, i, m, j, A);
}

子問題個(gè)數(shù) $a=2$
子問題數(shù)據(jù)規(guī)母耐В縮小倍數(shù) $b=2$
除遞歸外，主要時(shí)間花在合并上坟岔，它可以用 $f(n) = n$ 表示

$T(n) = 2T(\frac{n}{2}) + n$

此時(shí) $x=1=c$ 谒兄，時(shí)間復(fù)雜度 $\Theta(n\log{n})$

例9. 快速排序遞歸

algorithm quicksort(A, lo, hi) is 
  if lo >= hi || lo < 0 then 
    return
  
  // 分區(qū)
  p := partition(A, lo, hi) 
  
  // 遞歸
  quicksort(A, lo, p - 1) 
  quicksort(A, p + 1, hi)

子問題個(gè)數(shù) $a=2$
子問題數(shù)據(jù)規(guī)模縮小倍數(shù)
- 如果分區(qū)分的好社付， $b=2$
- 如果分區(qū)沒分好承疲，例如分區(qū)1 的數(shù)據(jù)是 0，分區(qū) 2 的數(shù)據(jù)是 $n-1$
除遞歸外鸥咖，主要時(shí)間花在分區(qū)上燕鸽，它可以用 $f(n) = n$ 表示

情況1 - 分區(qū)分的好

$T(n) = 2T(\frac{n}{2}) + n$

此時(shí) $x=1=c$ ，時(shí)間復(fù)雜度 $\Theta(n\log{n})$

情況2 - 分區(qū)沒分好

$T(n) = T(n-1) + T(1) + n$

此時(shí)不能用主定理求解

遞歸時(shí)間復(fù)雜度-展開求解

像下面的遞歸式扛或，都不能用主定理求解

例1 - 遞歸求和

long sum(long n) {
    if (n == 1) {
        return 1;
    }
    return n + sum(n - 1);
}

$T(n) = T(n-1) + c$ 绵咱， $T(1) = c$

下面為展開過程

$T(n) = T(n-2) + c + c$

$T(n) = T(n-3) + c + c + c$

...

$T(n) = T(n-(n-1)) + (n-1)c$

其中 $T(n-(n-1))$ 即 $T(1)$
帶入求得 $T(n) = c + (n-1)c = nc$

時(shí)間復(fù)雜度為 $O(n)$

例2 - 遞歸冒泡排序

void bubble(int[] a, int high) {
    if(0 == high) {
        return;
    }
    for (int i = 0; i < high; i++) {
        if (a[i] > a[i + 1]) {
            swap(a, i, i + 1);
        }
    }
    bubble(a, high - 1);
}

$T(n) = T(n-1) + n$ ， $T(1) = c$

下面為展開過程

$T(n) = T(n-2) + (n-1) + n$

$T(n) = T(n-3) + (n-2) + (n-1) + n$

...

$T(n) = T(1) + 2 + ... + n = T(1) + (n-1)\frac{2+n}{2} = c + \frac{n^2}{2} + \frac{n}{2} -1$

時(shí)間復(fù)雜度 $O(n^2)$

注：

等差數(shù)列求和為 $個(gè)數(shù)*\frac{\vert首項(xiàng)-末項(xiàng)\vert}{2}$

例3 - 遞歸快排

快速排序分區(qū)沒分好的極端情況

$T(n) = T(n-1) + T(1) + n$ 熙兔， $T(1) = c$

$T(n) = T(n-1) + c + n$

下面為展開過程

$T(n) = T(n-2) + c + (n-1) + c + n$

$T(n) = T(n-3) + c + (n-2) + c + (n-1) + c + n$

...

$T(n) = T(n-(n-1)) + (n-1)c + 2+...+n = \frac{n^2}{2} + \frac{2cn+n}{2} -1$

時(shí)間復(fù)雜度 $O(n^2)$

不會(huì)推導(dǎo)的同學(xué)可以進(jìn)入 https://www.wolframalpha.com/

例1 輸入 f(n) = f(n - 1) + c, f(1) = c
例2 輸入 f(n) = f(n - 1) + n, f(1) = c
例3 輸入 f(n) = f(n - 1) + n + c, f(1) = c

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市艾恼，隨后出現(xiàn)的幾起案子住涉，更是在濱河造成了極大的恐慌，老刑警劉巖钠绍，帶你破解...
沈念sama閱讀 217,185評(píng)論 6贊 503
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件舆声，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡柳爽，警方通過查閱死者的電腦和手機(jī)媳握，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,652評(píng)論 3贊 393
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來磷脯，“玉大人蛾找，你說我怎么就攤上這事≌允模” “怎么了打毛？”我有些...
開封第一講書人閱讀 163,524評(píng)論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵柿赊，是天一觀的道長。經(jīng)常有香客問我幻枉，道長碰声，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,339評(píng)論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任熬甫，我火速辦了婚禮胰挑，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘椿肩。我一直安慰自己洽腺，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,387評(píng)論 6贊 391
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布覆旱。她就那樣靜靜地躺著蘸朋，像睡著了一般。火紅的嫁衣襯著肌膚如雪扣唱。梳的紋絲不亂的頭發(fā)上藕坯，一...
開封第一講書人閱讀 51,287評(píng)論 1贊 301
城市分裂傳說
那天，我揣著相機(jī)與錄音噪沙，去河邊找鬼炼彪。笑死，一個(gè)胖子當(dāng)著我的面吹牛正歼，可吹牛的內(nèi)容都是我干的辐马。我是一名探鬼主播，決...
沈念sama閱讀 40,130評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼局义，長吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼喜爷！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起萄唇，我...
開封第一講書人閱讀 38,985評(píng)論 0贊 275
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤檩帐，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后另萤，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體湃密，經(jīng)...
沈念sama閱讀 45,420評(píng)論 1贊 313
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,617評(píng)論 3贊 334
?白月光啟示錄
正文我和宋清朗相戀三年四敞，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了泛源。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 39,779評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡忿危，死狀恐怖达箍，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情癌蚁，我是刑警寧澤幻梯，帶...
沈念sama閱讀 35,477評(píng)論 5贊 345
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布兜畸，位于F島的核電站，受9級(jí)特大地震影響碘梢，放射性物質(zhì)發(fā)生泄漏咬摇。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,088評(píng)論 3贊 328
男人毒藥：我在死后第九天來索命
文/蒙蒙一煞躬、第九天我趴在偏房一處隱蔽的房頂上張望岗憋。院中可真熱鬧奕剃，春花似錦旦部、人聲如沸霉晕。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,716評(píng)論 0贊 22
一樁弒父案雷客，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽芒珠。三九已至，卻和暖如春搅裙，著一層夾襖步出監(jiān)牢的瞬間皱卓，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 32,857評(píng)論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工部逮，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留娜汁，地道東北人。一個(gè)月前我還...
沈念sama閱讀 47,876評(píng)論 2贊 370
代替公主和親
正文我出身青樓兄朋，卻偏偏與公主長得像掐禁，于是被迫代替她去往敵國和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子颅和，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,700評(píng)論 2贊 354

Java數(shù)據(jù)結(jié)構(gòu)——遞歸

2.3 遞歸

概述

單路遞歸 Single Recursion

多路遞歸 Multi Recursion

遞歸優(yōu)化-記憶法

遞歸優(yōu)化-尾遞歸

遞歸時(shí)間復(fù)雜度-Master theorem[^14]

遞歸時(shí)間復(fù)雜度-展開求解

推薦閱讀更多精彩內(nèi)容