Python資料結構之遞迴方法詳解

2022-04-15 19:01:01

1.學習目標

遞迴函數是直接呼叫自己或通過一系列語句間接呼叫自己的函數。遞迴在程式設計有著舉足輕重的作用，在很多情況下，藉助遞迴可以優雅的解決問題。本節主要介紹遞迴的基本概念以及如何構建遞迴程式。

通過本節學習，應掌握以下內容：

理解遞迴的基本概念，瞭解遞迴背後蘊含的程式設計思想

掌握構建遞迴程式的方法

2.遞迴

2.1遞迴的基本概念

遞迴是一種解決問題的方法，它將問題不斷的分為更小的子問題，通過處理普通的子問題來解決問題。遞迴函數是直接呼叫自己或通過一系列語句間接呼叫自己的函數。需要注意的是，遞迴函數每次呼叫自己時，都會將原問題進行簡化，最終較小問題的序列必須收斂於基本情況，解決問題，終止遞迴。利用遞迴可以非常優雅的解決一些複雜問題。很多數學函數就是遞迴定義的，比如使用遞迴定義的階乘函數：

儘管這個定義是遞迴的，但它不是無限迴圈無法終止的。事實上，利用此函數可以非常簡單的計算階乘。例如計算3!，根據定義，有3!=3(3–1)!=3(2!)，接下來我們需要解決2!，再次應用定義 3! = 4(2!) = 3[(2)(2−1)!] = 3(2)(1!)，繼續此過程，最後我們需要計算0!，而根據定義0!=1，計算過程就結束了：

3!=3(2!)=3(2)(1!)=3(2)(1)(0!)=3(2)(1)(1)=6

可以看到，遞迴定義並非是無限迴圈的，因為每次應用定義，程式都會將問題分解為更簡單的子問題，在階乘函數範例中，即為計算較小數的階乘，直到計算0!，這不需要再次應用遞迴即可求解。當遞迴到底時，我們得到一個可以直接計算的閉合表示式，也被稱為遞迴的“基本情況”。而函數呼叫自身來執行子任務時，被稱為“遞迴情況”。

2.2遞迴的重要性

遞迴函數是從數學中借鑑的一種重要的程式設計技術，通常使用遞迴可以極大的降低程式碼量，在許多可以分解為子問題的任務中非常有用，例如，排序、遍歷和搜尋等通常可以藉助遞迴方法快速的給出解決方案。

2.3遞迴三原則

和許多演演算法一樣，遞迴同樣有著需要遵守的重要原則，稱為遞迴三原則：

遞迴演演算法必須有基本情況
遞迴演演算法必須改變狀態並逐漸收斂於基本情況
遞迴演演算法必須包含遞迴情況，能夠遞迴的呼叫自身

需要注意的是，遞迴的核心思想並不是迴圈，而是將問題分解成更小、更容易解決的子問題。

2.4遞迴的應用

遞迴在程式設計中有著十分重要的作用，以下是一些常用到遞迴的實際場景：

斐波那契數列、階乘計算等數學問題
歸併排序、快速排序
二分查詢
樹和圖的遍歷以及相關問題
漢諾塔

3.遞迴範例

本節中，我們將從簡單的列表求和問題入手，瞭解遞迴演演算法的使用方式，然後再瞭解如何解決經典遞迴問題——漢諾塔。

3.1列表求和

列表求和是十分簡單的問題，用來了解遞迴演演算法的思想再合適不過了。例如我們需要計算列表 [1, 2, 3, 4, 5] 的和，如果利用迴圈函數計算，則可以編寫如下程式碼計算列表中所有數之和：

def sum_list(list_data):
    result = 0
    for i in range(list_data):
        result += i
    return result

如果不使用迴圈，我們該如何解決這一問題呢？我們可以寫出求和過程((((1+2)+3)+4)+5)，而根據加法交換律，計算過程也可以寫為(1+(2+(3+(4+5))))，這時我們就可以很清楚的看到，列表的資料總和等於列表第一個元素加上其餘元素：

使用 python 實現以上等式如下：

def sum_list(list_data):
    if len(num_list) == 1:
        return list_data[0]
    else:
        return list_data[0] + sum_list(list_data[1:])

在程式碼中，首先給出了函數退出的條件，這就是遞迴函數的基本情況，在範例中就是說，長度為 1 的列表，其元素和就是列表中的數。不滿足退出條件，sum_list 則會呼叫自己，這就是遞迴函數的遞迴情況，也是其稱為遞迴函數的原因。

在下圖(a)中，可以看到求解 [1, 2, 3, 4, 5] 時的遞迴呼叫過程，每次遞迴呼叫都是在解決一個更接近基本情況的問題，直到問題不能被進一步簡化。

當問題無法簡化時，開始拼接所有子問題的解，下圖(b)展示遞迴函數 sum_list 在返回一系列呼叫結果時所進行的加法操作，當返回到頂層時，就解決了最初的問題。

3.2漢諾塔(Towers of Hanoi)問題

漢諾塔(Towers of Hanoi)是一道十分經典的謎題。它由三個塔和許多不同尺寸的圓盤組成，這些圓盤可以移動到任何杆上。開始時圓盤按尺寸升序排列在一個塔上，頂部的圓盤最小，底部圓盤最大。謎題的目標是將疊好的圓盤移動到另一個杆，且滿足以下規則：

一次只能移動一個圓盤
較大圓盤不能放在較小的圓盤上

接下來我們講解如何藉助一根中間塔 Auxiliary，將高度為 n 的一疊圓盤從起始塔 Source 移到終點塔 Destination：

藉助終點塔 Destination，將頂部的 n - 1 個圓盤從 Source 移動到 Auxiliary
將第 n 個圓盤從 Source 塔移動到終點塔 Destination
藉助 Source 塔，將 n - 1 個磁碟從輔助塔 Auxiliary 移動到終點塔 Destination

只要遵循漢諾塔的移動規則，就可以遞迴地執行上述步驟。最簡單的漢諾塔是隻有一個盤子，在這種情況下，只需將這個盤子移到終點柱子 Destination 即可，這就是基本情況。上述遞迴步驟通過逐漸減小高度 n 來向基本情況靠近，如下圖所示：

演演算法的關鍵在於進行兩次遞迴呼叫，第一次遞迴是將除了最後一個圓盤以外的其他所有圓盤從 Source 塔移到輔助塔 Auxiliary 。然後將最後一個圓盤移到終點塔 Destination。第二次遞迴是將圓盤從 Auxiliary 移到 Destination：

def towersOfHanoi(number, source=1, destination=3, auxiliary=2):
    if number >= 1:
        towersOfHanoi (number - 1, source, auxiliary, destination)
        print("Move disk %d from tower %d to tower %d" % (number, source, destination))
        towersOfHanoi (number - 1, auxiliary, destination, source)
towersOfHanoi(number=3)

程式輸出如下所示：

Move disk 1 from tower 1 to tower 3
Move disk 2 from tower 1 to tower 2
Move disk 1 from tower 3 to tower 2
Move disk 3 from tower 1 to tower 3
Move disk 1 from tower 2 to tower 1
Move disk 2 from tower 2 to tower 3
Move disk 1 from tower 1 to tower 3

以上就是Python資料結構之遞迴方法詳解的詳細內容，更多關於Python 資料結構遞迴的資料請關注it145.com其它相關文章！