再帰検索ブール戻り関数

Question

ブール値を返す再帰関数検索（l、key）を作成します。そうでなければFalse。基本ケースと、より小さな問題が大きな問題にどのように関係するかを記述します。 in演算子やindex（）リストメソッドは使用できません。

誰も私が説明のためにここで行う必要があることを説明することはできますか？私はどこで始めるべきかを知るために何かを知っていません。試験ラボの試験のための試験です。

ここに私が提供したコードがあります。

def search(l,key): 
    """ 
    locates key in list l. if present, returns True; else returns False. 
    PRE: l is a list. 
    POST: l is unchanged; returns True if key in l; False otherwise. 
    """ 

サンプルメイン：

l1 = [1, '2', 'x', 5, -2] 

print search(l1, 'x') # should output: "True" 

print search(l1, 2)  # should output: "False" 

Answer 1

すべての再帰が同じルールに従う傾向：

• は、一つ以上の終端ケースを持っています。
• 他のすべてのケースは、現在のケースのやや簡単な形式です。ゼロである
  • b場合、返却：

  ので、例えば、（非常に非効率的な）方法は、2つの正の数値aとbを追加します。

• その他の場合は、2つの数字a+1とb-1を追加します。

ような何か：

def addtwo (a, b): 
    if b == 0: 
     return a 
    return addtwo (a+1, b-1) 

は、今度は、あなたの割り当てのための例について考えてみましょう：リストが空の場合

• 、あなたはそれを見つけることができませんでした：falseを返します。
• リストの最初の要素が自分のキーと等しい場合、それを見つけました：trueを返します。
• それ以外の場合は、最初の要素を削除したリストを参照してください。擬似コードで

（はPythonに似ていますが、いくつかの作業を行う必要があるでしょうことを十分に異なる非常にである）：

def search (list, key): 
    if list is empty: 
     return false 
    if key == first item in list: 
     return true 
    return search (list with first element removed, key) 

Answer 2

再帰に関するすべての質問が同じに対処する必要があります方法（通常は）私はlistにはkeyありません特定することができたときに...、

だからこの質問では、自問してみてください... base caseが何であるかを自問してみてください、次に高い場合のためにその上に構築.. 。 リストが空のときは明らかですが、それが存在しないことは確かです。それは keyと同じかどう

大きなリストについては、あなたが最初の要素を比較し、あなたはすぐにTrueを返しますが、包み、それはないですが、あなたはrest of the listのために、すべてのチェックを実行....

これらのすべての側面を勉強して、 あなたのアルゴリズムはここにあります。

function locate(lst,key) 
    if lst == emptylist then return False 
    if lst[0] == key then return True 
    else return locate(lst[1..],key) //i use the notation lst[1...] to indicate list starting from 1 index.