Having trouble implementing recursion in Python

Question

I've read as many recursion threads as possible but I'm still kind of lost. I'm not looking for anyone to specifically code this for me but I would greatly appreciate some direction.

I have a big block of JSON that I have imported into Python as a dictionary. I have a function that will look through the records and add the IDs to a list. However, this function will only look at the first "level" of children. Can someone suggest how I begin to call this function recursively so it will follow the tree for however many levels deep it goes?

BTW, my data is essentially a dichotomous tree so I need it to follow multiple branching paths.

Here is the very messy function I have currently:

def addFighter(fighterDict, database):
    childID = [child["id"] for child in fighterDict["children"]]
    database.append(childID)

    for child in childID:
        addFighter(child)

I know my for loop is wrong, but I'm not sure where to find the proper resources that will explain the next steps.

Thank you for your help!

Edit:

Yes, I meant dichotomous tree. Sorry if this is not a CS term. I come from a wildlife biology background. :)

My data is a Brazilian jiujitsu black belt lineage. For example, Mitsuyo Maeda trained Luis Franca and Carlos Gracie Sr. Luis Franca trained Oswaldo Fadda, who trained 9 people. Carlos Gracie Sr. trained 21 people and so on. The data is many levels deep and contains 1,664 black belts.

I have converted my data from JSON to a big nested dictionary. I'm trying to convert it to a flat dictionary so it can be imported into Postgres using Psycopg2. My end goal is to have a table that lists a fighter in one column and the second column would be a list of IDs or named of the people they trained.

Edit2:

Snippet of code: (I'm not sure of the best way to format this here)

{"id":-301,"name":"The Beginning","data":"Mitsoyo Maeda, children [id]","children":    [{"id":467,"name":"Takeo Iano ","data":"Mitsoyo Maeda, children [id]","children":[{"id":974536,"name":"Francisco Sa ","data":"Mitsoyo Maeda, children [id]","children":[{"id":975533,"name":"Daniel Beleza ","data":"Mitsoyo Maeda, children [id]","children":[]},{"id":1168951,"name":"Carlos Pinto Sa ","data":"Mitsoyo Maeda, children [id]","children":[{"id":1169948,"name":"Reginaldo de Almeida ","data":"Mitsoyo Maeda, children [id]","children":[]},{"id":1272639,"name":"Ademir Oliveira ","data":"Mitsoyo Maeda, children [id]","children":[]},{"id":1273636,"name":"Daniel Taveras ","data":"Mitsoyo Maeda, children [id]","children":[]}]}]}]},{"id":1464,"name":"Mitsuyo Maeda ","data":"Mitsoyo Maeda, children [id]","children":[{"id":2461,"name":"Luis Franca ","data":"Mitsoyo Maeda, children [id]","children":[{"id":4455,"name":"Oswaldo Fadda ","data":"Mitsoyo Maeda, children [id]","children":[{"id":83218,"name":"Sergio Amarel ","data":"Mitsoyo Maeda, children [id]","children":[]},{"id":84215,"name":"Ronald Bauer ","data":"Mitsoyo Maeda, children [id]","children":[{"id":1230765,"name":"Victor da Costa ","data":"Mitsoyo Maeda, children [id]","children":[]}]},{"id":85212,"name":"Beto Ferrao ","data":"Mitsoyo Maeda, children [id]","children":[{"id":160984,"name":"Andre Assuncao ","data":"Mitsoyo Maeda, children [id]","children":[]}]},

It would help to see a data example and what field exactly you want to pull out. — Paulo Bu
– Paulo Bu, Commented Feb 13, 2014 at 21:51
What's a dichotomous tree? Google only turns up forestry results, not CS. — user2357112
– user2357112, Commented Feb 13, 2014 at 21:52
I'm surprised that you don't get a TypeError when calling addFighter with only one argument. Or did you copy-paste your code incorrectly? — 2rs2ts
– 2rs2ts, Commented Feb 13, 2014 at 22:04

Stephen · Accepted Answer · 2014-02-13 22:07:02Z

2

That looks pretty close. From what I understand of the situation, this would be more appropriate:

database = []

def addFighter(fighterDict, database):
  # add this fighters id to the database
  database.append(fighterDict["id"])

  # get children if any
  children = fighterDict.get("children", [])

  for child in children:
    # for each child, run the addFighter method
    addFighter(child, database)

addFighter(someDictOfFighters, database)

print database

So, it seems like you have fighter dictionaries, that at least contain ids and a children key with values that are more fighter dictionaries. So something like: {"id": 1, "children": [{"id": 2, "children": [{"id": 4}]}, {"id": 3}]}. Think I got that right.

Passing this to the function, it gets the first id (1) and adds it to the database. It then sees the children (with ids 2 and 3) and runs the function on each of them.

For id 2, it adds 2 to the database, then runs the function on its children (4).

4 has no children so it adds 4 to the database, gets an empty list for the children and doesn't run any more recursion.

We then go up all the way back to the first instance of the function, and call it on the dict with id 3. 3 will be added to the database, and an empty list will exist for the children, and the function will not be called again from there.

We head back out to the first call, and we are done with the for loop. We know have, assuming database was a list, database = [1, 2, 4, 3].

edited Feb 13, 2014 at 22:07

answered Feb 13, 2014 at 21:57

Stephen

2152 silver badges7 bronze badges

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

2 Comments

2rs2ts Over a year ago

This function won't return anything. Are you sure that's helpful?

Stephen Over a year ago

So you would have to initialize an empty list beforehand and pass it to the function as database. Then look at the database variable after.

Collectives™ on Stack Overflow

Having trouble implementing recursion in Python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related