CODEWITHSUNDEEP
pythonrecursion
Kara
Kara

Reputation: 785

Recursive function that takes in a list and an integer and returns the integer in the list in order

So let's say I this function:

squeeze([1,4,7,9], 8)
squeeze([1,4,7,9], 0)

I would want the function to return a new list containing:

[1,4,7,8,9]
[0,1,4,7,9]

I want to make this function using recursion, but I'm having trouble

def squeeze(x:list, num:int):
    if len(x) == 1:
        if num < x[0]:
            return [num] + x #if the integer is less than the 1st value, put it in the front
        elif x[0] < num < x[2]: 
            return [x[0]] + [num] + [x[2]] #put it in the list
         #insert this number into the correct spot
    else: 
        return squeeze(num, x[0:1]) + squeeze(num, x[1:]) #i don't think this is right

I'm having trouble comparing the numbers in the list and putting it in the correct spot by using recursion.

Upvotes: 0

Views: 778

Answers (2)

Phil Cooper
Phil Cooper

Reputation: 5877

OK, there is already an answer upvoted and accepted BUT on the chance that this is not just a leaning/homework thing and someone actually wants to do this, there's a module for this.

check out what's available in bisect. 

from bisect import insort

a = [1,4,7,9]
insort(a, 10)
print a

a = [1,4,7,9]
insort(a, 8)
print a

a = [1,4,7,9]
insort(a, 0)
print a

output is what is expected but there is also insort_left and insort_right to fine-tune your policy on ties.

Note: this does not return a new list, it modifies the old but is easily wrapped with a copy of the original first leaving you with a two line squeeze function.

Upvotes: 0

thefourtheye
thefourtheye

Reputation: 239573

You can do like this

def squeeze(myList, num):
    if myList == []:
        return [num]
    elif num > myList[0]:
        return [myList[0]] + squeeze(myList[1:], num)
    else:
        return [num] + myList

print squeeze([1,4,7,9], 10)
print squeeze([1,4,7,9], 8)
print squeeze([1,4,7,9], 0)

Output

[1, 4, 7, 9, 10]
[1, 4, 7, 8, 9]
[0, 1, 4, 7, 9]

Explanation

  1. If myList is empty, return the num as list
  2. If the num is greater than the first element of the myList, num cannot fit here. So, we recurse further leaving the first element of the myList behind. (myList[1:] means that without 0th element). For example, myList is [4, 7, 9] and num is 8. So, we leave 4 behind and recurse with [7, 9] and 8, still 8 is greater than 7, so now we recurse with [9] this time, 8 is smaller than 9, so we return [8, 9] by the else part. And when the recursion unwinds, we get [7, 8, 9] and then finally [4, 7, 8, 9]
  3. If the num is lesser than or equal to first element of myList, then that is where we need to place num. So, we simply place num at the beginning of myList and return it.

Upvotes: 3

Related Questions