Recursive function without loops or variables

Question

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?

Because at last iteration there won't be an element with index 1.. — Olvin Roght
– Olvin Roght, Commented Jan 13, 2021 at 21:43
An important part of recursion is testing the base case. Eventually there will be one thing left in the list. — Kenny Ostrom
– Kenny Ostrom, Commented Jan 13, 2021 at 21:44
This is a poor way to implement it, since slicing a list creates a copy. — wim
– wim, Commented Jan 13, 2021 at 21:46

Chayim Friedman · Accepted Answer · 2021-01-13 21:45:20Z

2

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:])

answered Jan 13, 2021 at 21:45

Chayim Friedman

76.1k5 gold badges96 silver badges140 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

chepner · Accepted Answer · 2021-01-13 21:45:38Z

1

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:])

answered Jan 13, 2021 at 21:45

chepner

538k77 gold badges594 silver badges746 bronze badges

Comments

zvone · Accepted Answer · 2021-01-13 21:47:15Z

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:])

Jasmijn · Accepted Answer · 2021-01-13 21:48:12Z

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 ;)

Collectives™ on Stack Overflow

Recursive function without loops or variables

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related