代碼小工蟻的#《算法圖解》#學(xué)習(xí)筆記-C3遞歸
C3 遞歸recursion

一、調(diào)用棧

執(zhí)行棧（execution stack），又稱控制棧（control stack）、運(yùn)行時(shí)棧（run-time stack）和調(diào)用棧（call stack）。
棧(stack)是限定僅在表尾進(jìn)行壓入（插入）和彈出（刪除并讀?。┎僮鞯木€性表。
表尾端稱為棧頂(top)，相應(yīng)地，表頭端稱為棧底(bottom)。^[1]
棧遵循LIFO后進(jìn)先出（Last In First Out）原則。

壓入（插入）push (insert)
彈出（刪除并讀?。﹑op (remove and read)

調(diào)用棧保持程序調(diào)用的返回地址，以及本地變量、參數(shù)傳遞、環(huán)境傳遞等數(shù)據(jù)。
無(wú)限遞歸（Infinite recursion）或過(guò)多的堆棧層級(jí)（占用大量的內(nèi)存）會(huì)導(dǎo)致堆棧溢出（stack overflow）

一般而言，高級(jí)語(yǔ)言會(huì)將調(diào)用棧的細(xì)節(jié)隱藏至后臺(tái)。

擴(kuò)展：
世界上最大的開(kāi)發(fā)者社區(qū)StackOverflow：
https://stackoverflow.com/

二、遞歸

從一個(gè)故事開(kāi)始的遞歸：

從前有座山，山里有座廟，廟里有個(gè)老和尚，正在給小和尚講故事呢！故事是什么呢？
從前有座山，山里有座廟，廟里有個(gè)老和尚，正在給小和尚講故事呢！故事是什么呢？
從前有座山，山里有座廟，廟里有個(gè)老和尚，正在給小和尚講故事呢！故事是什么呢？
……

從前有座山，山里有座廟...圖片來(lái)源知乎[2]

在計(jì)算機(jī)中，遞歸是指一種通過(guò)重復(fù)將問(wèn)題分解為同類的子問(wèn)題的方法。
換一種表述就是函數(shù)自己調(diào)用自己。
每個(gè)遞歸函數(shù)都有兩個(gè)條件：基線條件base case和遞歸條件recursive case。
基線條件：函數(shù)不再調(diào)用自己，避免無(wú)限循環(huán)。
遞歸條件：函數(shù)調(diào)用自己。

好處：遞歸使函數(shù)的定義和算法的描述比使用非遞歸方法更簡(jiǎn)明。

遞歸的強(qiáng)大之處在于它允許用戶用有限的語(yǔ)句描述無(wú)限的對(duì)象。
因此，在計(jì)算機(jī)科學(xué)中，遞歸可以被用來(lái)描述無(wú)限步的運(yùn)算，盡管描述運(yùn)算的程序是有限的。
——Nicklaus Wirth（對(duì)，就是提出“算法+數(shù)據(jù)結(jié)構(gòu)=程序”的尼古拉斯·沃斯）^[3]

缺點(diǎn)：遞歸調(diào)用可能占用大量的內(nèi)存。
處理：重寫代碼改用循環(huán)；使用尾遞歸tail recursion。

遞歸應(yīng)用：求階乘5！
5！= 5 * 4 * 3 * 2 * 1

代碼片斷：

def fact(x):
    if x == 1:
        return 1
    else:
        return x*fact(x-1)

print('5! = ', fact(5))

注意代碼中的基線條件與遞歸條件。
python中已有 math.factorial() 方法可直接求階乘。

擴(kuò)展：遞歸典型問(wèn)題：梵塔問(wèn)題（漢諾塔問(wèn)題）

相傳在古印度圣廟中，有一種被稱為漢諾塔(Hanoi)的游戲。
該游戲是在一塊銅板裝置上，有三根桿(編號(hào)A、B、C)，在A桿自下而上、由大到小按順序放置64個(gè)金盤。
游戲的目標(biāo)：把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好。
操作規(guī)則：每次只能移動(dòng)一個(gè)盤子，并且在移動(dòng)過(guò)程中三根桿上都始終保持大盤在下，小盤在上，操作過(guò)程中盤子可以置于A、B、C任一桿上。^[4]

網(wǎng)絡(luò)圖片-漢諾塔玩具（侵刪）

C語(yǔ)言源碼參考^[5]

代碼片斷：

# coding=utf-8

# 漢諾塔問(wèn)題演示

def hanoi(n, p1, p2, p3):
    # 移動(dòng)步數(shù)steps，全局變量
    global steps
    steps += 1
    if n == 1:
        print('Move sheet {} from {} to {}.'.format(n, p1, p3))
        print('-' * 30)
    else:
        hanoi(n-1, p1, p3, p2)
        print('Move sheet {} from {} to {}'.format(n, p1, p3))
        hanoi(n-1, p2, p1, p3)
    return steps


if __name__ == '__main__':
    n = int(input('請(qǐng)輸入盤數(shù)1-8：'))
    # 移動(dòng)步數(shù)統(tǒng)計(jì)steps
    steps = 0
    steps_num = hanoi(n,'A', 'B', 'C')
    print(steps_num)