Insert a number in a sorted list and return the list with the number at the correct index
Recursion is usually a poor choice in Python.  Non-tail recursion is usually a poor choice in any language (and this is non-tail because we apply + to the result before returning it).

It's better to use the standard bisect module to find (once) the correct index at which to insert.  This module provides the bisect() function to locate the correct index, and also the insort() function that calls bisect and then inserts, exactly as we want:

insert = bisect.insort


This will insert in place, rather than creating a new list, so not exactly equivalent to the existing code.



As you say "using only simple functions", let's suppose you can't use the Standard Library (that's a bad assumption in general - Python philosophy is that it "includes batteries" to make your code simpler).  Then we can use a similar method to write our own non-recursive version.

def insert(lst, to_insert):
    """
    parameters : lst: sorted list (smallest to largest)
                 to_insert: value to add
    returns : copy of lst with the to_insert value added in sorted position
    """

    # binary search
    left = 0
    right = len(lst)

    while left != right:
        mid = left + (right-left) // 2
        if lst[mid] == to_insert:
            left = right = mid
        elif lst[mid] &lt; to_insert:
            left = mid + 1
        else:
            right = mid

    # now copy the list, inserting new element
    return lst[:left] + [to_insert] + lst[left:]




Since the question states (without justification) that "recursion is mandatory", I recommend making the search recursive, but performing the insertion just once:

#! untested
def insert(lst, to_insert, left=0, right=None):
    if right is None:
        right = len(lst)

    if left == right:
        return lst[:left] + [to_insert] + lst[left:]

    else:
        mid = left + (right-left) // 2
        if lst[mid] == to_insert:
            left = right = mid
        elif lst[mid] &lt; to_insert:
            left = mid + 1
        else:
            right = mid
        # move left or right, then
        return insert(lst, to_insert, left, right)


This is now tail-recursive, at least, and only reallocates the list elements once, rather than every level of recursion.