3

Say I have a list x = [1, 2, 3, 4]

Is there a recursive method where i can go through the list to find the value?

I want to ultimately be able to compare a returned value in the list, (or nested list) to an arbitrary number to see it it matches.

I can think a way to do this using a for loop, but i have trouble imagining a recursive method to do the same thing. I know that I can't set a counter to keep track of my position in the list because calling the function recursively would just reset the counter every time.

I was thinking I could set my base case of the function as a comparison between the number and a list of len 1.

I just want some hints really.

user3272601
  • 33
  • 1
  • 1
  • 3

4 Answers4

2

This is not the way to do things in Python, but surely - you can traverse a list of lists recursively:

def findList(lst, ele):
    if not lst:         # base case: the list is empty
        return False
    elif lst[0] == ele: # check if current element is the one we're looking
        return True
    elif not isinstance(lst[0], list): # if current element is not a list
        return findList(lst[1:], ele)
    else:                              # if current element is a list
        return findList(lst[0], ele) or findList(lst[1:], ele)
Óscar López
  • 232,561
  • 37
  • 312
  • 386
  • it works - can see that the recursion works my slicing the 'top' of the list off ever time: I'm trying to apply this to nested lists and it's not working - I added an elif statement that calls the function on a sublist if one of the elements on the list are found as type list. and the function doesn;t work on deeper lists. – user3272601 Feb 04 '14 at 21:23
0

Recursive functions are idiomatic for when you have a linked list. Python lists are more like arrays. But it's still possible to handle a Python list with a recursive function -- there's no real utility, but it can be interesting as an exercise.

You start with a full list, and your base case is when the list is empty. Traverse the list by passing the list in as an argument, using x.pop() to simultaneously fetch and remove the first item in the list, evaluate the popped item, and then pass the list (now shorter) into the same function.

Edit: actually, on second thought, you would be better off not using x.pop() and instead peeking at the first value and passing the remainder in a slice. This would be grossly inefficient, because you're copying the list every time you slice, but it's better than destructively consuming the list inside your recursive function, unless that's a desired side-effect.

Andrew Gorcester
  • 19,595
  • 7
  • 57
  • 73
0

Well you will have two base cases:

1) You have reached the end of the list => return false.

2) Your current element is the element you are looking for => return true (or the element or its position, whatever you are interested in).

The thing you have to do all the time is check both base cases on the current element and apply the function recursively on the next element in the list if neither one of the base cases applied.

fedorSmirnov
  • 701
  • 3
  • 9
  • 19
0

You could try this simple recursive solution without the need of slicing the list.

  1. We check if the current element that we are iterating is an instance of <class 'list'> then we need to call the function again (recursion).

  2. Otherwise we know that we have got some value. So in that if condition we are checking, if search element is equal to that value if it is true, then the search element is found, otherwise we are just simply printing the value we got.

def find_rec(lst, val):
    for ele in lst:
        if isinstance(ele, list): 
            find_rec(ele, val) #recursive function
        else:
            if ele == val:
                print("Found", val)
            else:
                print(ele)

lst = [[1, [10, 20, 30], 100, 200], [999, 120]]
find_rec(lst, 200)
Ajay S
  • 29
  • 4