一、遞歸

概念：

　　函數直接或者間接的調用自身算法的過程，則該函數稱為遞歸函數。在計算機編寫程序中，遞歸算法對解決一大類問題是十分有效的。

特點：

　　①遞歸就是在過程或者函數里調用自身。

　　②在使用遞歸策略時，必須有一個明顯的結束條件，稱為遞歸出口。問題規模相比上次遞歸有所減少，

　?、圻f歸算法解題通常顯得很簡潔，但遞歸算法解題的效率較低。所以一般不倡導使用遞歸算法設計程序。

　?、茉谶f歸調用的過程當中系統的每一層的返回點、局部變量等開辟了棧來存儲。遞歸函數次數過多容易造成棧溢出等。

　　所以一般不倡導用遞歸算法設計程序。

要求：

遞歸算法所體現的"重復"一般有三個條件：

　　①每次在調用規模上都有所縮小（通常是減半）。

　　②相鄰兩次重復之間有緊密的聯系，前一次要為后一次做準備（通常前一次的輸出就作為后一次的輸入）。

　?、墼趩栴}的規模極小時必須用直接解答而不再進行遞歸調用，因而每次遞歸調用都是有條件的（以規模未達到直接解答的大小為條件），

無條件的遞歸調用將會成為死循環而不能正常結束。

分析以下函數的執行過程：

def func3(x): if x>0: print(x) func3(x-1)func3(5)def func4(x): if x>0: func4(x-1) print(x)func4(5)

　　根據Python執行的過程，及函數調用去分析執行結果！

?關于斐波拉契數列

　　斐波拉契數列指的是這樣一個數列：0， 1， 1， 2， 3， 5， 8， 13， 21， 34， 55， 89， 144， 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368。

特別注意：第0項是0，第1項是第一個1。這個數列從第2項開始，每一項都等于前兩項之和。

def fibo(n):before = 0after = 1if n == 0 or n == 1:return nif n <= 3:return 1return fibo(n-1)+fibo(n-2)print(fibo(3)) 斐波那契數列

二分查找

　　從有序列表的候選區data[0:n]開始，通過對待查找的值與候選區中間值的比較，可以使候選區減少一半。

特點：

　　二分查找算法就是不斷將數組進行對半分割，每次拿中間元素和要找的元素進行比較。小就向右找，大就向左找！

要求：　　

　　在一段數字內，找到中間值，判斷要找的值和中間值大小的比較。
　　　　如果中間值大一些，則在中間值的左側區域繼續按照上述方式查找。
　　　　如果中間值小一些，則在中間值的右側區域繼續按照上述方式查找。
　　直到找到我們希望的數字。

def search_data(data,data_find):# 中間值的索引號的定義：數組長度/2mid = int(len(data)/2)# 判斷從1開始的數字數組內查找if data[mid] >= 1:# 如果我們要找的值（data_find）比中間值（data[mid]）小if data[mid] > data_find:print("你要找的數字比中間值[%s]小..." % data[mid])# 在中間值（data[mid]）的左側繼續查找，在此函數中繼續循環 search_data(data[:mid],data_find)# 如果我們要找的值（data_find）比中間值（data[mid]）大elif data[mid] < data_find:print("你要找的數字比中間值[%s]大..." % data[mid])# 在中間值（data[mid]）的右側繼續查找，在此函數中繼續循環 search_data(data[mid:],data_find)else:# 如果我們要找的值（data_find）既不比中間值（data[mid]）大，也不比中間值（data[mid]）小，則就是它print("這就是你要找的[%s]！" % data[mid])else:print("不好意思，沒有找到你要的值...")if __name__ == '__main__':# 創建一個1到6000萬的連續數字數組data = list(range(60000000))# 調用函數找到95938的值search_data(data,95938) 相關代碼舉例

列表查找

列表查找：從列表中查找指定元素
　　輸入：列表、待查找元素
　　輸出：元素下標或未查找到元素

一般是有兩種方法：

1、順序查找

　　從列表第一個元素開始，順序進行搜索，直到找到為止。

def linear_search(data_set,value):for i in data_set:if data_set[i] == value:return i

2、二分查找

　　從有序列表的候選區data[0:n]開始，通過對待查找的值與候選區中間值的比較，可以使候選區減少一半。

def bin_search(data_set,value):low = 0high = len(data_set)-1while low <= high:mid = (low+high)//2if data_set[mid] == value:return midelif data_set[mid] > value:high = mid - 1else:low = mid + 1 def bin_search(data_set,value,low,high):if low <= high:mid = (low+high)//2if data_set[mid] == value:return midelif data_set[mid] >value:return bin_search(data_set,value,low,high)else:return bin_search(data_set, value, low, high)else:return 二分查找遞歸版

練習題：

現有一個學員信息列表（按id增序排列），格式為：[{"id":1001, "name":"張三", "age":20},{"id":1002, "name":"李四", "age":25},{"id":1004, "name":"王五", "age":23},{"id":1007, "name":"趙六", "age":33}]修改二分查找代碼，輸入學生id，輸出該學生在列表中的下標，并輸出完整學生信息。 l = [{"id":1001, "name":"張三", "age":20},{"id":1002, "name":"李四", "age":25},{"id":1004, "name":"王五", "age":23},{"id":1007, "name":"趙六", "age":33} ]def bin_search(data_set,value):"""二分查找:param data_set: 列表:param value: 要查的值:return:"""low = 0high = len(data_set)-1while low <= high:mid = (low+high)//2if data_set[mid]['id'] == value:return (mid,data_set[mid])elif data_set[mid]['id'] > value:high = mid - 1else:low = mid + 1else:return (0,None)flog = True while flog:sid = input("請輸入學號(退出：Q)：").strip()if sid.isdigit():if sid.upper() == "Q":flog = Falseelse:sid = int(sid)mid,infos = bin_search(l,sid)if not infos:print("查無此人！！！")else:s = "學生學號:{id},姓名:{name},年齡:{age}".format(**infos)print("該學生所在信息索引坐標：%s"%mid)print("該學生的所有信息：%s"%s)

?

轉載于:https://www.cnblogs.com/zh605929205/p/7467231.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的算法前戏 递归 二分查找 列表查找的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。