To iterate is human, to recurse, divine.
人理解迭代，神理解遞歸溯香。

什么是遞歸

遞歸算法（英語(yǔ)：recursion algorithm）在計(jì)算機(jī)科學(xué)中是指一種通過重復(fù)將問題分解為同類的子問題而解決問題的方法螟够。遞歸式方法可以被用于解決很多的計(jì)算機(jī)科學(xué)問題，因此它是計(jì)算機(jī)科學(xué)中十分重要的一個(gè)概念。

簡(jiǎn)單地說众旗，就是如果在函數(shù)中存在著調(diào)用函數(shù)本身的情況，這種現(xiàn)象就叫遞歸趟畏。

「遞歸」贡歧，先有「遞」再有「歸」，「遞」的意思是將問題拆解成子問題來解決赋秀， 子問題再拆解成子子問題利朵，...，直到被拆解的子問題無需再拆分成更細(xì)的子問題（即可以求解）猎莲，「歸」是說最小的子問題解決了绍弟，那么它的上一層子問題也就解決了，上一層的子問題解決了著洼，上上層子問題自然也就解決了

遞歸的兩個(gè)條件：

• 可以通過遞歸調(diào)用來縮小問題規(guī)模樟遣，且新問題與原問題有著相同的形式。（自身調(diào)用）
• 存在一種簡(jiǎn)單情境身笤，可以使遞歸在簡(jiǎn)單情境下退出豹悬。（遞歸出口）

遞歸算法的一般形式：

def f(mode):
    if end_condition:  # 遞歸出口
        end
    else:
        f(mode_small)  # 遞歸本身，遞歸

階乘

一個(gè)數(shù)的階乘是遞歸簡(jiǎn)單而典型的例子液荸，階乘的遞推公式為：factorial(n)=n*factorial(n-1)瞻佛，其中n為非負(fù)整數(shù),且0!=1,1!=1

def factorial(i):
    """階乘"""
    if i < 0:
        return
    elif i <= 2:
        return i
    else:
        return i * factorial(i-1)

遞歸過程

遞歸

這個(gè)調(diào)用的過程和棧的工作原理一樣，遞歸調(diào)用就是通過棧這種數(shù)據(jù)結(jié)構(gòu)完成的娇钱。整個(gè)過程實(shí)際上就是一個(gè)棧的入棧和出棧的問題伤柄。

遞歸中的"遞"就是入棧，"歸"就是出棧文搂。

入棧和出棧 的過程：

def 遞歸(n):
    print("遞進(jìn)：" + str(n))
    if n > 0:
        遞歸(n-1)
    print("回歸：" + str(n))
遞歸(3)

output:

遞進(jìn)：3
遞進(jìn)：2
遞進(jìn)：1
遞進(jìn)：0
回歸：0
回歸：1
回歸：2
回歸：3

遞歸過程：

image

遞歸算法解決思路

套路：

1. 明確你這個(gè)函數(shù)想要干什么
2. 尋找遞歸結(jié)束條件
3. 找出函數(shù)的等價(jià)關(guān)系式（遞歸中最難的一步）

經(jīng)典例題

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

形如 1适刀、1、2煤蹭、3笔喉、5、8疯兼、13然遏、21贫途、34 ...的數(shù)列

1. 由這個(gè)數(shù)列我們可以容易發(fā)現(xiàn)其遞推公式：f(n)=f(n-1)+f(n-2)
2. 遞歸結(jié)束條件：當(dāng)n=1或者n=2時(shí)吧彪，f(1)=f(2)=1

def fibonacci(i):
    """斐波那契數(shù)列"""
    if i <= 2:
        return 1
    else:
        return fibonacci(i-1) + fibonacci(i-2)

2.猴子吃桃子

猴子第一天摘下若干個(gè)桃子，當(dāng)即吃了一半丢早，還不過癮姨裸，又多吃了一個(gè)秧倾，第二天早上又將剩下的桃子吃掉一半，又多吃了一個(gè)傀缩。以后每天早上都吃前一天剩下的一半零一個(gè)那先。到第10天早上想再吃時(shí)，見只剩下一個(gè)桃子了赡艰。求第一天共摘多少個(gè)桃子售淡？

1. 最后一天時(shí)，只剩下一個(gè)桃子 (結(jié)束條件)
2. 當(dāng)天的桃子等于上一天加一的和乘二 (monkey(n-1)+1)*2

def monkey(n):
    """猴子分桃"""
    if n == 1:
        return 1
    else:
        return (monkey(n-1)+1)*2

3.漢諾塔問題

漢諾塔

相傳在古印度圣廟中慷垮，有一種被稱為漢諾塔(Hanoi)的游戲揖闸。該游戲是在一塊銅板裝置上，有三根桿(編號(hào)A料身、B汤纸、C)，在A桿自下而上芹血、由大到小按順序放置64個(gè)金盤(如下圖)贮泞。游戲的目標(biāo)：把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好幔烛。操作規(guī)則：每次只能移動(dòng)一個(gè)盤子啃擦，并且在移動(dòng)過程中三根桿上都始終保持大盤在下，小盤在上说贝，操作過程中盤子可以置于A议惰、B、C任一桿上乡恕。

解題方法：

1. 將最上面的n-1個(gè)圓盤從初始位移動(dòng)到過渡位

2. 將初始位的最底下的一個(gè)圓盤移動(dòng)到目標(biāo)位

3. 將過渡位的n-1個(gè)圓盤移動(dòng)到目標(biāo)位

• 當(dāng)只剩下一個(gè)盤子時(shí)言询，直接移動(dòng)到C （結(jié)束條件）
• 將n-1只盤子看成整體，通過c移動(dòng)到b,然后a移動(dòng)到c傲宜，最后b處的n-1只盤子經(jīng)過a移動(dòng)到c

def hanoi(n, a, b, c):  # a為初始位运杭，b為過渡位，c為目標(biāo)位
    """漢諾塔"""
    if n == 1:
        print(a, '-->', c)
    else:
        hanoi(n-1, a, c, b)  # 初始位為a,通過c移動(dòng)到b
        print(a, '-->', c)
        hanoi(n-1, b, a, c)  # 初始位為b,通過a移動(dòng)到c

4. 反轉(zhuǎn)單鏈表

反轉(zhuǎn)一個(gè)單鏈表函卒。

示例:

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

1. 結(jié)束條件：當(dāng)鏈表為空表或者只有一個(gè)節(jié)點(diǎn)
2. 遞的操作：
   1.得到尾部節(jié)點(diǎn):new_head = self.reverseList(head.next)
   2.翻轉(zhuǎn)當(dāng)前節(jié)點(diǎn)：head.next.next = head
   3.拆掉當(dāng)前節(jié)點(diǎn)的next：head.next = None

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        """反轉(zhuǎn)單鏈表"""
        if head is None or head.next is None:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

適用遞歸的問題

1. 數(shù)據(jù)的定義是按遞歸定義的辆憔。如Fibonacci函數(shù)。
2. 問題解法按遞歸算法實(shí)現(xiàn)报嵌。如Hanoi問題虱咧。
3. 數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的。如二叉樹锚国、廣義表等腕巡。

遞歸和遞推的異同

遞推和遞歸有著很多的相似之處，遞推甚至可以看做是遞歸的反方向血筑，但對(duì)比其細(xì)節(jié)是存在很多不同的绘沉。

遞歸法：把問題轉(zhuǎn)化為規(guī)模更小的子問題解決煎楣，思考的重點(diǎn)在于建立原問題和子問題之間的聯(lián)系。有的問題有很明確的遞歸結(jié)構(gòu)车伞，但是需要仔細(xì)的思考择懂，才能正確的轉(zhuǎn)化為結(jié)構(gòu)相同的子問題。

遞推法：根據(jù)已知信息不斷的計(jì)算出未知信息另玖，直到得到結(jié)果困曙，思考的重點(diǎn)在于“步步為營(yíng)”。

尾遞歸

尾遞歸相對(duì)傳統(tǒng)遞歸谦去，其是一種特例赂弓。在尾遞歸中，先執(zhí)行某部分的計(jì)算哪轿，然后開始調(diào)用遞歸盈魁，所以你可以得到當(dāng)前的計(jì)算結(jié)果，而這個(gè)結(jié)果也將作為參數(shù)傳入下一次遞歸窃诉。這也就是說函數(shù)調(diào)用出現(xiàn)在調(diào)用者函數(shù)的尾部杨耙，因?yàn)槭俏膊浚云溆幸粋€(gè)優(yōu)越于傳統(tǒng)遞歸之處在于無需去保存任何局部變量飘痛，從內(nèi)存消耗上珊膜，實(shí)現(xiàn)節(jié)約特性。

普通遞歸調(diào)用：

def recursion(n):
    if n==1:
        return n
    else:
        return n+recursion(n-1)  

調(diào)用這個(gè)函數(shù)recursion（5）宣脉，編譯器會(huì)執(zhí)行：

recursion(5)
5+recursion(4)
5+(4+recursion(3))
5+(4+(3+recursion(2)))
5+(4+(3+(2+recursion(1))))
5+(4+(3+(2+1)))
15

此處編譯器會(huì)分配遞歸棧來保存中間結(jié)果下來看尾遞歸實(shí)現(xiàn)：

 def tail_recursion(n,total=0):
        if n==0:
            return total
        else:
            return tail_recursion(n-1,  total+n)  

此時(shí)车柠，編譯器做的工作：

tail_recursion(5,0)
tail_recursion(4,5)
tail_recursion(3,9)
tail_recursion(2,12)
tail_recursion(1,14)
tail_recursion(0,15)
15

你可以看到當(dāng)前時(shí)刻的計(jì)算值作為第二個(gè)參數(shù)傳入下一個(gè)遞歸，使得系統(tǒng)不再需要保留之前計(jì)算結(jié)果塑猖。

但是python本身不支持尾遞歸（沒有對(duì)尾遞歸做優(yōu)化）竹祷，而且對(duì)遞歸的次數(shù)有限制，當(dāng)遞歸深度超過1000時(shí)羊苟，會(huì)拋出異常塑陵。

總結(jié)

遞歸是非常基礎(chǔ)的算法蜡励，思考遞歸時(shí)要拋棄程序設(shè)計(jì)的細(xì)節(jié)

1. 明確遞歸函數(shù)功能

2. 遞歸程序出口設(shè)計(jì)

3. 遞歸要有規(guī)模遞減

遞歸思想在動(dòng)態(tài)規(guī)劃令花，回溯算法，二叉樹的深度優(yōu)先搜索等都有密切的涉及凉倚。