Recursive functions on a list of tuples

Question

I have the following problem:

First of all, I have a list of tuples like the following:

[(1,2),(2,3),(4,5),(5,6),(5,7),(5,8),(6,9),(6,10),(7,11),(12,14)]

To make things easier let's say that the first number in each tuple 'controls' the second (for those who are familiar with dependency parsing, the first number represents the index of the head, while the second the index of the dependent).

Now what I want to create is function that takes as argument an int and the list above. The function has to look for all the tuples that have as first number the integer argument and return the second number. The function should then recursively take each of these second number, look what are the tuples where it appears as first number and return the second number. This should go on until no other second numbers can be retrieved.

I will use an example to explain it better: let's say that this function takes as input the number 5. The tuples having 5 as first number are (5,6),(5,7),(5,8); as first result the function should then take 6,7,8 and append it to a list. Now the function should consider 6,7,8 , look for the tuples where they appear as first numbers ((6,9),(6,10),(7,11)) and return the second numbers (9,10,11). Since 8 does not appear as first number in any of the tuples, its journey ends at this stage. The final list returned should then be [6,7,8,9,10,11].

I have tried something like that but it doesn't work:

def foo(start_index, lista_tuples,list_to_return=list()):

    indeces=[x[1] for x in lista_tuples if x[0]==start_index]
    list_to_return.extend(indeces)
    for index in indeces:
              foo(index,lista_tuples,list_to_return)
    return list_to_return

but it doesn't work. Can someone help me?

@inspectorG4dget: Isn't he? `foo(index,lista_tuples,list_to_return)` — David Robinson, Jul 26 '13 at 19:19
Seems to work for me. Can you add a complete non working example? — Dek Dekku, Jul 26 '13 at 19:21
This seems to work for me: `foo(5, [(1,2),(2,3),(4,5),(5,6),(5,7),(5,8),(6,9),(6,10),(7,11),(12,14)])` returns `[6,7,8,9,10,11]` just like you say it should. — David Robinson, Jul 26 '13 at 19:21
Oh geez! Withdrawn (also, scheduling appointment with eye doctor). — inspectorG4dget, Jul 26 '13 at 19:21
You should really be using a `defaultdict(list)` (or even just a `dict`) for this mapping instead of a list of tuples. You'd get much cleaner syntax and better lookup performance. (Also, `indices` is not spelled that way.) — user2357112, Jul 26 '13 at 19:29
Careful with that [mutable default argument](http://stackoverflow.com/questions/1132941/least-astonishment-in-python-the-mutable-default-argument), by the way! Do you really want to use the same list every time the call doesn't explicitly provide one? — user2357112, Jul 26 '13 at 19:31

score 1 · Answer 1 · answered Jul 26 '13 at 19:25

>>> L =[(1,2),(2,3),(4,5),(5,6),(5,7),(5,8),(6,9),(6,10),(7,11),(12,14)]
>>> def foo(start, L, answer=None):
...     if answer is None:
...         answer = []
...     answer += [i[1] for i in L if i[0]==start]
...     for i in (i[1] for i in L if i[0]==start):
...             foo(i, L, answer)
...     return answer
...
>>> print foo(5, L)
[6, 7, 8, 9, 10, 11]

score 1 · Accepted Answer · answered Jul 26 '13 at 19:25

In your code you always iterate over all the "second values" you found. This can generate infinite recursion. To avoid it, remove from indeces all the values that are already in list_to_return:

def foo(start_index, lista_tuples,list_to_return=list()):

    indeces=[x[1] for x in lista_tuples if x[0]==start_index]
    new_values = list(set(indeces) - set(list_to_return))
    list_to_return.extend(indeces)
    for index in new_values:
              foo(index,lista_tuples,list_to_return)
    return list_to_return

The double conversion list->set->list is a little overkill, but it took three seconds to write down :D

EDIT: In fact, you should actually use a set. This will avoid duplicates.

Thank you! Yes, in fact I had this very problem and could not figure out what was the cause.. — user1718064, Jul 26 '13 at 22:03
You're welcome. Also, follow user2357112 suggestion in the comments, otherwise your function will only work once. (The default argument is one of the few things that Python got wrong in my opinion.) — Dek Dekku, Jul 27 '13 at 06:37

Roman Pekar · Answer 3 · 2013-07-26T19:32:19.600

1

functional way

def worker(n):
    data = []
    for j in [x[1] for x in l if x[0] == n]:
        data += [j] + worker(j)
    return data

print worker(5)
[6, 9, 10, 7, 11, 8]

procedural way

def worker(n, data):
    for j in [x[1] for x in l if x[0] == n]:
        data.append(j)
        worker(j, data)

d = []
worker(5, d)
print d
[6, 9, 10, 7, 11, 8]

edited Jul 26 '13 at 19:32

answered Jul 26 '13 at 19:25

Roman Pekar

107,110
28
195
197

score 0 · Answer 4 · edited May 23 '17 at 12:21

You should check out this popular question which may explain why using a mutable default value in your function may be causing you issues.

def foo(start_index, lista_tuples):
    return _foo(start_index, lista_tuples, [])

def _foo(start_index, lista_tuples,list_to_return):

    indeces=[x[1] for x in lista_tuples if x[0]==start_index]
    list_to_return.extend(indeces)
    for index in indeces:
              _foo(index,lista_tuples,list_to_return)
    return list_to_return

Recursive functions on a list of tuples

4 Answers4