ソート済みリストに整数を再帰的に追加する - 再帰的に

Question

intにリストを再帰的に追加し、後で追加機能を追加する必要があります。

def insert_in_list(x, tree): 
    if not tree: 
     return tree 
    elif isinstance(tree[0], list): 
     return inserting(x, tree[0]) + inserting(x, tree[1:]) 
    elif x < tree[0]: 
     tree.insert(0, x) 
     return tree 
    else: 
     return inserting(x, tree[1:]) 

私はinsert()を使用しています。しかし何らかの理由で私のリストは3つの値に制限されているようです。たとえば

>>> insert_in_list(2, [1,5,10]) 
[2,5,10] 

1には何が起こったでしょうか？

Answer 1

最後のケースで最初の値が破棄されるためです。最初にinsert_in_list(x, tree)に電話し、ケース4で終了します（insert_in_list(x, [5, 10])と呼びます）。その後、ケース3で終了し、xを最初の位置に挿入し、新しいリスト[2, 5, 10]を返します。

それはインデックスに対処する方が簡単でしょう：あなたのtreeがソートされている場合、あなたができることを

>>> insert_in_list(2, [1,5,10]) 
[1, 2, 5, 10] 

注：それは、あなたの質問には無関係だったので、私はちょうど第二ケースを残し

def insert_in_list(x, tree, index=0): 
    if not tree: 
     return tree 
    elif x < tree[index]: 
     tree.insert(index, x) 
     return tree 
    else: 
     return insert_in_list(x, tree, index+1) 

値が挿入されるべき場所を見つけるために再帰の代わりに二等分をする。再帰的な二分で例えばとbisect.insort_rightに基づく：しかし

def insert_in_list(x, tree, lo=0, hi=None): 
    if not tree: 
     return tree 

    if hi is None: 
     hi = len(tree) 
    if lo < hi: 
     mid = (lo + hi) // 2 
     if x < tree[mid]: 
      hi = mid 
     else: 
      lo = mid + 1 
     return insert_in_list(x, tree, lo, hi) 

    tree.insert(lo, x) 
    return tree