CODEWITHSUNDEEP
pythonrecursion
Justin
Justin

Reputation: 41

How can I rewrite this method to recursive?

It is a simple program for counting the number of element in a list where the element is bigger or equal to x and smaller of equal to y.

def NumRange(a,x,y):
    count = 0
    for num in a:
        if(num>=x and num<=y):
            count+=1
    return count

NumRange([1,3,5,7,9,11],3,9)
# => 4

How can I rewrite this method to be recursive? I know that I may need to add one more parameter in this method but I have no idea how to do.

Upvotes: 1

Views: 105

Answers (8)

Yuval Atzmon
Yuval Atzmon

Reputation: 5945

Here is another variant, in a single line. It relies on python's conditional evaluation order

def NumRange(a,x,y,ix=0):
    return (ix != len(a)) and ((x<= a[ix] <=y) + NumRange(a, x,y, ix+1))

Upvotes: 0

Yuval Atzmon
Yuval Atzmon

Reputation: 5945

As mentioned above, since slicing a list creates a new copy. All of the above methods are memory hungry.

Here is a memory efficient and concise solution that uses an index argument without slicing the list

def NumRange(a,x,y,ix=0):
    if ix == len(a):
        return 0

    return (a[ix]>=x and a[ix]<=y) + NumRange(a, x,y, ix+1)

Upvotes: 0

Przemysław Zalewski
Przemysław Zalewski

Reputation: 3986

You should consider optimizing for a tail call by using an accumulator. Down below you can see variation of @Keiwan's answer using some nice features like destructuring assigment.

def NumRange(a,x,y):
  def rec (a, acc) : 
    if not a:  # base case - if the list if empty return the accumulated result
      return acc

    head, tail = a[0], a[1:]   # destructure list to the first item and all the rest

    incr = int(x <= head and head <= y)  # acts as the increment
    return rec(tail, acc + incr)  # recursively process rest of the list

  return rec(a, 0)  # pass the list and an empty accumulator to the implementation

Upvotes: 1

Keiwan
Keiwan

Reputation: 8251

You can do it like this:

def NumRangeRec(a,x,y):
    if not a:  # checks if the list is empty
        return 0
    incr = int(x <= a[0] and a[0] <= y)  # acts as the increment
    return NumRangeRec(a[1:], x, y) + incr  # pass the tail of the list to the recursive call

Here, the increment (incr) is set to 0 or 1 based on the result of the condition. You can use int(some boolean) to convert the boolean result to 0 or 1.

(Technically, since TRUE and FALSE are 1 and 0 in Python you don't necessarily need this. However, in Python 2 True and False can be reassigned so using int(..) puts you on the safe side.)

Upvotes: 1

Abhinav Desor
Abhinav Desor

Reputation: 397

A possible solution:

def NumRange(a, x, y):
    # Base case
    if not a:
        return 0

    if x <= a[0] <= y:
        return 1 + NumRange(a[1:], x, y)
    else:
        return NumRange(a[1:], x, y)

Upvotes: 1

ForceBru
ForceBru

Reputation: 44838

def NumRange(a, x, y):
    if not a:
        return 0
    if a[0] >= x and a[0] <= y:
        return 1 + NumRange(a[1:], x, y)
    return NumRange(a[1:], x, y)

First you need to define an edge condition: return 0 if the list is empty. If the condition isn't satisfied, you continue testing other candidates by calling the function recursively. So you return something other than zero if it is satisfied. You pass the 'tail' of the list (the list without its first element) with a[1:].

Upvotes: -1

roman
roman

Reputation: 117380

>>> def NumRangeRec(a,x,y):
...     if not a:
...         return 0
...     elif a[0] >= x and a[0] <= y:
...         return 1 + NumRangeRec(a[1:],x,y)
...     else:
...         return NumRangeRec(a[1:],x,y)
... 
>>> NumRangeRec([1,3,5,7,9,11],3,9)
4

Upvotes: 0

Eli Sadoff
Eli Sadoff

Reputation: 7308

This is a great candidate for recursion, in Python 2 you can do it like this

def NumRange(a, x, y):
    hd, tl = a[0], a[1:]
    if tl == []:
        return 1 if hd >= x and hd <= y else 0
    else:
        return (1 if hd >= x and hd <= y else 0) + NumRange(tl, x, y)

This is tail recursive as well.

Upvotes: 1

Related Questions