Python的遞歸和列表

我正在學習有關在Python遞歸和我有這樣的代碼：Python的遞歸和列表

def search(l,key): 
    """ 
    locates key in list l. if present, returns location as an index; 
    else returns False. 
    PRE: l is a list. 
    POST: l is unchanged; returns i such that l[i] == key; False otherwise. 
    """ 

    if l: # checks if list exists 
     if l[0] == key:  # base case - first index is key 
      return True 

     s = search(l[1:], key)  # recursion 
     if s is not False:   
      return s 

    return False   # returns false if key not found

有人能向我解釋，行

s = search(l[1:], key)

做究竟是什麼？ [1：]對列表做了什麼？

來源

2014-02-09 gptt916

[here]（http://stackoverflow.com/questions/509211/pythons-slice-notation） –

humm，代碼似乎並沒有'返回我這樣l [i] == key' – laike9m

的常用方法遞歸遍歷函數式編程語言列表是使用head取決於訪問列表（命名爲car，first的第一個元素的功能，語言）以及訪問列表其餘部分的另一個功能（cdr，rest,tail）。在Python沒有一個直接等同於那些功能，但我們可以此爲同樣的效果，使用slices：

lst[0] # first element of a list 
lst[1:] # rest of the elements in the list, after the first

例如，在Python遞歸搜索函數，確定元素是否是與否在列表中（謂語，因爲它返回True或False）是這樣的：

def search(lst, key): 
    if not lst:   # base case: list is empty 
     return False 
    elif lst[0] == key: # base case: current element is searched element 
     return True 
    else:    # recursive case: advance to next element in list 
     return search(lst[1:], key)

考慮到上面的例子中，可以很容易地適應它，解決了原來的問題 - 如何返回的索引列表中的元素（如果找到）或False（如果未找到）：

def search(l, key): 
    if not l: 
     return False 
    elif l[0] == key: 
     return 0 
    else: 
     idx = search(l[1:], key) 
     return 1+idx if idx is not False else False

來源

2014-02-09 14:37:19

謝謝！我會upvote你的答案，但我沒有足夠的代表D： – gptt916

編輯：它適用於嵌套列表，但是當我用這個搜索[[1，[2,3]，4，[5，[6， []，[8,9]]，10]]，8）'它不返回任何東西？哦，還修改了我的代碼，以便它返回true iff s存在於L – gptt916

要添加到上面的評論，經過一些測試後，它只適用於嵌套列表，如果嵌套列表是列表中的最後一個元素。我不知道爲什麼會發生這種情況D： – gptt916

它遞歸調用search函數，從l切片數據。 l[1:]表示除索引1之外的所有數據。例如，

data = [1, 2, 3, 4, 5] 
print data[1:]   # [2, 3, 4, 5] 
print data[2:]   # [3, 4, 5]

您可以使用切片表示法來獲取範圍之間的值，例如

print data[1:4]   # [2, 3, 4] 
print data[2:3]   # [3]

您還可以得到，直到特定索引的所有元素（不包括索引處的元素）

print data[:4]   # [1, 2, 3, 4] 
print data[:3]   # [1, 2, 3]

有時你可能不知道從最終的元素的索引。所以，你可以使用負的索引，這樣

print data[-2:]   # [4, 5] 
print data[1:-2]   # [2, 3] 
print data[:-3]   # [1, 2]

當您使用負的索引，最後一個元素爲代表，-1，最後卻一個與-2等。你可以閱讀更多關於這個切片符號在此excellent answer.

來源

2014-02-09 14:35:00 thefourtheye

哦，我明白了，所以它只是繼續使用對元素的搜索，當它下降時，它每次都排除索引0？ – gptt916

@NickGong正確:) – thefourtheye

很酷。這是發生遞歸的地方（如您所注意的），通過調用函數本身給定相同的key，但列表l（不包括第一個元素）的子集。

基本上，它會一直這樣做直到列表中找到key。如果是這樣，True將被退回。否則，整個列表將被清除，直到列表爲空（所有元素已經檢查與key相等，此時，算法放棄並返回False。

這將告訴你key是否在列表中，但不能找到哪個索引。

來源

2014-02-09 14:39:06 bnjmn

Python的遞歸和列表

回答

相關問題