CODEWITHSUNDEEP
pythonpython-3.xrecursion
Samjohns081998
Samjohns081998

Reputation: 141

Recursive function without loops or variables

I am learning coding by myself. I am taking learning recursive function from online resources, and as an exercise, I came across this one exercise where I am tasked to create a recursive function to see if numbers in the list are in order. The exercise says not to use loops and not to use variables, so I can learn recursive function better for the future.

 def is_increasing(lst):
  if not (lst[0]) < lst[1]:
    return False
  else:
    return is_increasing(lst[1:])

when I input is_increasing([1,2,12,24]) in the console.

The errors says:

IndexError:list index out of range

What am I doing wrong that is showing this error?

Upvotes: 0

Views: 1579

Answers (4)

Jasmijn
Jasmijn

Reputation: 10452

Your function never returns True. That's not directly the cause of the error, but that's related to it.

For a recursive function that returns a bool, you need two base cases, not just one: one that returns True and one that returns False.

So when should it return True? What is the relevant base case? It is when the list is too small to fail: a list that is of length 1 or 0 is always increasing, technically. And in that case, there is no lst[1], which causes the IndexError. So this is the solution:

def is_increasing(lst):
    if len(lst) < 2:
        return True
    elif lst[0] >= lst[1]:
        return False
    else:
        return is_increasing(lst[1:])

(You also had a mistake where you compare not lst[0] with lst[1], I fixed that for you ;)

Upvotes: 1

zvone
zvone

Reputation: 19352

When implementing a recursive function, there is always one special case which has to be handled differently: how does the recursion stop?

The implementation show here correctly reduces the problem of solving an input of size N to a problem of size N-1:

def is_increasing(lst):
  if not (lst[0]) < lst[1]:
    return False
  else:
    return is_increasing(lst[1:])

What is missing is handling the situation where the size is 0 or 1. Therefore:

def is_increasing(lst):
    if len(lst) < 2:
        return True  # That is always sorted

    # BTW this is correct only if it is supposed to be descending,
    # oherwise it should be lst[0] > lst[1] 
    if not lst[0] < lst[1]:
        return False
    else:
        return is_increasing(lst[1:])

Upvotes: 1

chepner
chepner

Reputation: 531115

You didn't take the recursion far enough. You are assuming that a list will have at least two elements, but that's not true for empty and singleton lists. (Plus, at no point did you ever attempt to return True.)

The true base case is a list with fewer than 2 items, which is trivially sorted. Otherwise, you can check whether the first 2 elements are in order, then recursively check the rest of the list.

def is_increasing(lst):
    if len(lst) < 2:
        return True
    else:
        return lst[0] < lst[1] and is_increasing(lst[1:])

Upvotes: 1

Chayim Friedman
Chayim Friedman

Reputation: 70940

You need a stop condition (or base case) for every recursive function, otherwise it won't stop: in your case, the stop condition is if the list contains one elements or less, it's always sorted:

 def is_increasing(lst):
  if len(lst) <= 1: return True # Base case

  if not (lst[0]) < lst[1]:
    return False
  else:
    return is_increasing(lst[1:])

Upvotes: 2

Related Questions