欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python數(shù)據(jù)結(jié)構(gòu)之遞歸方法詳解

 更新時間:2022年04月15日 16:05:31   作者:盼小輝丶  
這篇文章主要為大家介紹了遞歸的基本概念以及如何構(gòu)建遞歸程序。通過本章的學(xué)習(xí),大家可以理解遞歸的基本概念,了解遞歸背后蘊含的編程思想以及掌握構(gòu)建遞歸程序的方法,需要的可以參考一下

1.學(xué)習(xí)目標(biāo)

遞歸函數(shù)是直接調(diào)用自己或通過一系列語句間接調(diào)用自己的函數(shù)。遞歸在程序設(shè)計有著舉足輕重的作用,在很多情況下,借助遞歸可以優(yōu)雅的解決問題。本節(jié)主要介紹遞歸的基本概念以及如何構(gòu)建遞歸程序。

通過本節(jié)學(xué)習(xí),應(yīng)掌握以下內(nèi)容:

理解遞歸的基本概念,了解遞歸背后蘊含的編程思想

掌握構(gòu)建遞歸程序的方法

2.遞歸

2.1遞歸的基本概念

遞歸是一種解決問題的方法,它將問題不斷的分為更小的子問題,通過處理普通的子問題來解決問題。遞歸函數(shù)是直接調(diào)用自己或通過一系列語句間接調(diào)用自己的函數(shù)。需要注意的是,遞歸函數(shù)每次調(diào)用自己時,都會將原問題進(jìn)行簡化,最終較小問題的序列必須收斂于基本情況,解決問題,終止遞歸。利用遞歸可以非常優(yōu)雅的解決一些復(fù)雜問題。很多數(shù)學(xué)函數(shù)就是遞歸定義的,比如使用遞歸定義的階乘函數(shù):

盡管這個定義是遞歸的,但它不是無限循環(huán)無法終止的。事實上,利用此函數(shù)可以非常簡單的計算階乘。例如計算3!,根據(jù)定義,有3!=3(3–1)!=3(2!),接下來我們需要解決2!,再次應(yīng)用定義 3! = 4(2!) = 3[(2)(2−1)!] = 3(2)(1!),繼續(xù)此過程,最后我們需要計算0!,而根據(jù)定義0!=1,計算過程就結(jié)束了:

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

可以看到,遞歸定義并非是無限循環(huán)的,因為每次應(yīng)用定義,程序都會將問題分解為更簡單的子問題,在階乘函數(shù)示例中,即為計算較小數(shù)的階乘,直到計算0!,這不需要再次應(yīng)用遞歸即可求解。當(dāng)遞歸到底時,我們得到一個可以直接計算的閉合表達(dá)式,也被稱為遞歸的“基本情況”。而函數(shù)調(diào)用自身來執(zhí)行子任務(wù)時,被稱為“遞歸情況”。

2.2遞歸的重要性

遞歸函數(shù)是從數(shù)學(xué)中借鑒的一種重要的編程技術(shù),通常使用遞歸可以極大的降低代碼量,在許多可以分解為子問題的任務(wù)中非常有用,例如,排序、遍歷和搜索等通??梢越柚f歸方法快速的給出解決方案。

2.3遞歸三原則

和許多算法一樣,遞歸同樣有著需要遵守的重要原則,稱為遞歸三原則:

  • 遞歸算法必須有基本情況
  • 遞歸算法必須改變狀態(tài)并逐漸收斂于基本情況
  • 遞歸算法必須包含遞歸情況,能夠遞歸的調(diào)用自身

需要注意的是,遞歸的核心思想并不是循環(huán),而是將問題分解成更小、更容易解決的子問題。

2.4遞歸的應(yīng)用

遞歸在程序設(shè)計中有著十分重要的作用,以下是一些常用到遞歸的實際場景:

  • 斐波那契數(shù)列、階乘計算等數(shù)學(xué)問題
  • 歸并排序、快速排序
  • 二分查找
  • 樹和圖的遍歷以及相關(guān)問題
  • 漢諾塔

3.遞歸示例

本節(jié)中,我們將從簡單的列表求和問題入手,了解遞歸算法的使用方式,然后再了解如何解決經(jīng)典遞歸問題——漢諾塔。

3.1列表求和

列表求和是十分簡單的問題,用來了解遞歸算法的思想再合適不過了。例如我們需要計算列表 [1, 2, 3, 4, 5] 的和,如果利用循環(huán)函數(shù)計算,則可以編寫如下代碼計算列表中所有數(shù)之和:

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

如果不使用循環(huán),我們該如何解決這一問題呢?我們可以寫出求和過程((((1+2)+3)+4)+5),而根據(jù)加法交換律,計算過程也可以寫為(1+(2+(3+(4+5)))),這時我們就可以很清楚的看到,列表的數(shù)據(jù)總和等于列表第一個元素加上其余元素:

使用 python 實現(xiàn)以上等式如下:

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

在代碼中,首先給出了函數(shù)退出的條件,這就是遞歸函數(shù)的基本情況,在示例中就是說,長度為 1 的列表,其元素和就是列表中的數(shù)。不滿足退出條件,sum_list 則會調(diào)用自己,這就是遞歸函數(shù)的遞歸情況,也是其稱為遞歸函數(shù)的原因。

在下圖(a)中,可以看到求解 [1, 2, 3, 4, 5] 時的遞歸調(diào)用過程,每次遞歸調(diào)用都是在解決一個更接近基本情況的問題,直到問題不能被進(jìn)一步簡化。

當(dāng)問題無法簡化時,開始拼接所有子問題的解,下圖(b)展示遞歸函數(shù) sum_list 在返回一系列調(diào)用結(jié)果時所進(jìn)行的加法操作,當(dāng)返回到頂層時,就解決了最初的問題。

3.2漢諾塔(Towers of Hanoi)問題

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

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

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

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

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

算法的關(guān)鍵在于進(jìn)行兩次遞歸調(diào)用,第一次遞歸是將除了最后一個圓盤以外的其他所有圓盤從 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數(shù)據(jù)結(jié)構(gòu)之遞歸方法詳解的詳細(xì)內(nèi)容,更多關(guān)于Python 數(shù)據(jù)結(jié)構(gòu)遞歸的資料請關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • python process模塊的使用簡介

    python process模塊的使用簡介

    在python中大部分情況需要使用多進(jìn)程,python提供了multiprocessing模塊。multiprocessing模塊的功能眾多:支持子進(jìn)程、通信和共享數(shù)據(jù)、執(zhí)行不同形式的同步,提供了Process、Queue、Pipe、Lock等組件。本文將著重講解process模塊的使用
    2021-05-05
  • Python加載帶有注釋的Json文件實例

    Python加載帶有注釋的Json文件實例

    今天小編就為大家分享一篇Python加載帶有注釋的Json文件實例,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-05-05
  • python使用mysql數(shù)據(jù)庫示例代碼

    python使用mysql數(shù)據(jù)庫示例代碼

    本篇文章主要介紹了python使用mysql數(shù)據(jù)庫示例代碼,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-05-05
  • python實現(xiàn)圖像識別功能

    python實現(xiàn)圖像識別功能

    這篇文章主要為大家詳細(xì)介紹了python實現(xiàn)圖像識別功能,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-01-01
  • 用Python爬取某乎手機APP數(shù)據(jù)

    用Python爬取某乎手機APP數(shù)據(jù)

    最近爬取的數(shù)據(jù)都是網(wǎng)頁端,今天來教大家如何爬取手機端app數(shù)據(jù)(本文以ios蘋果手機為例,其實安卓跟ios差不多)! 本文將以『某乎』為實戰(zhàn)案例,手把手教你從配置到代碼一步一步的爬取App數(shù)據(jù),需要的朋友可以參考下
    2021-06-06
  • python list等分并從等分的子集中隨機選取一個數(shù)

    python list等分并從等分的子集中隨機選取一個數(shù)

    這篇文章主要介紹了python list等分并從等分的子集中隨機選取一個數(shù),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-11-11
  • 使用Gitee自動化部署python腳本的詳細(xì)過程

    使用Gitee自動化部署python腳本的詳細(xì)過程

    小編最近在自學(xué)python,在學(xué)習(xí)過程中有好多意向不到的收獲,真的很開心,今天重點給大家分享使用Gitee自動化部署python腳本的詳細(xì)過程,包括安裝環(huán)境搭建及一些注意事項,感興趣的朋友跟隨小編一起看看吧
    2021-05-05
  • Python實現(xiàn)視頻字幕時間軸格式轉(zhuǎn)換的示例

    Python實現(xiàn)視頻字幕時間軸格式轉(zhuǎn)換的示例

    本文主要介紹了Python實現(xiàn)視頻字幕時間軸格式轉(zhuǎn)換的示例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-11-11
  • python實現(xiàn)批量修改圖片格式和尺寸

    python實現(xiàn)批量修改圖片格式和尺寸

    這篇文章主要為大家詳細(xì)介紹了python實現(xiàn)批量修改圖片格式和尺寸的方法,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-06-06
  • Python3爬蟲中關(guān)于Ajax分析方法的總結(jié)

    Python3爬蟲中關(guān)于Ajax分析方法的總結(jié)

    在本篇文章里小編給大家整理的是一篇關(guān)于Python3爬蟲中關(guān)于Ajax分析方法的總結(jié),需要的朋友們可以學(xué)習(xí)下。
    2020-07-07

最新評論