Recursive functions

[Ayman_2001]

Greetings,
I've been doing this course on Udacity and this one problem has been stressing me for a while and I don't know why this keeps coming back to me and I can't really get a idea of it due to the fact that I find recursive functions super confusing and complicated.

I would like to find the solution by myself but I need some help to how this works and why it doesn't output in my desired manner. Thank you.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

# Single Gold Star       # Family Trees       # In the lecture, we showed a recursive definition for your ancestors. For this # question, your goal is to define a procedure that finds someone's ancestors, # given a Dictionary that provides the parent relationships.       # Here's an example of an input Dictionary:       ada_family = { 'Judith Blunt-Lytton': ['Anne Isabella Blunt', 'Wilfrid Scawen Blunt'],               'Ada King-Milbanke': ['Ralph King-Milbanke', 'Fanny Heriot'],               'Ralph King-Milbanke': ['Augusta Ada King', 'William King-Noel'],               'Anne Isabella Blunt': ['Augusta Ada King', 'William King-Noel'],               'Byron King-Noel': ['Augusta Ada King', 'William King-Noel'],               'Augusta Ada King': ['Anne Isabella Milbanke', 'George Gordon Byron'],               'George Gordon Byron': ['Catherine Gordon', 'Captain John Byron'],               'John Byron': ['Vice-Admiral John Byron', 'Sophia Trevannion'] }       # Define a procedure, ancestors(genealogy, person), that takes as its first input # a Dictionary in the form given above, and as its second input the name of a # person. It should return a list giving all the known ancestors of the input # person (this should be the empty list if there are none). The order of the list # does not matter and duplicates will be ignored.   output = [] def ancestors(genealogy, person):     if person in genealogy:         for candidate in genealogy[person]:             output.append(candidate)             ancestors(genealogy, candidate)         return output     else:         return []                         # Here are some examples:       print (ancestors(ada_family, 'Augusta Ada King')) #>>> ['Anne Isabella Milbanke', 'George Gordon Byron', #    'Catherine Gordon','Captain John Byron']       print (ancestors(ada_family, 'Judith Blunt-Lytton')) #>>> ['Anne Isabella Blunt', 'Wilfrid Scawen Blunt', 'Augusta Ada King', #    'William King-Noel', 'Anne Isabella Milbanke', 'George Gordon Byron', #    'Catherine Gordon', 'Captain John Byron']       print (ancestors(ada_family, 'Dave')) #>>> []

[Gribouillis]

The output list that is defined at line 26 should be defined inside the body of the ancestors() function otherwise all the calls to ancestors() will share the same output list and this can only fail. Each time the function is called, a new output list must be created.

Then at line 31, you are computing the ancestors of the candidate by a recursive call but you are not doing anything with the list of ancestors that is returned by that call. If you don't use the result, this call is unnecessary, or perhaps there is something to change in the code.

[Ayman_2001]

Then how should I do it?? to get my desired output? I've made prior attempts to declare the output variable inside the ancestor function but still failed to get my desired results.

[ndc85430]

Show the attempt with having output local to the function.

Have you tried other resources to try and get your head around recursion? I believe I suggested "Grokking Algorithms" in one of your other threads.

Recursion isn't too complicated an idea. It's about solving a problem that can be expressed in terms of smaller and smaller versions of the same problem. A really simple example of this idea can be seen when we use recursion to find the sum of the values in a sequence:

1 2 3 4 5 6 7 8 9 10 11 12

def sum_values(values):     def find_sum(sum_so_far, values_left):         if len(values_left) == 0:             return sum_so_far         else:             current_sum = sum_so_far + values_left[0]             remaining_values = values_left[1:]             return find_sum(current_sum, remaining_values)       return find_sum(0, values)   print(sum_values((1, 2, 3)))

Here, sum_values defines its own function called find_sum that actually does the recursion. Let's examine how it works. We call it on line 10 with values of sum_so_far = 0 and values_left = values, which should make sense: before we do any adding up, we start our sum at 0 and we want to sum up all the items, so we pass our entire sequence values. Let's look at the else branch first, since that's the interesting one. We compute the current sum by taking what we have already (the 0 we passed in) and the first value in the sequence (line 6). Since we've now accounted for that value in our sum, we no longer need to consider it, so the remaining values we do have to consider are just all but that first value (line 7). Well, remaining_values is just another sequence, with one fewer element than we started with (so in my example, it'll be (2, 3) here). So, we can just use find_sum again, but passing in our current_sum and remaining_values. In that second call, sum_so_far = 1 and values_left = (2, 3). We end up in the else branch again and now call find_sum(3, (3, )). In that call, we're still in the else branch. We compute current_sum = 6 and remaining_values = () and so call find_sum(6, ()). Now, we find values_left has nothing in it, so we end up in the if branch and return the value of sum_so_far, which is 6 as expected. Of course, that value of 6 is returned from each of the nested recursive calls, until we get back to the call in sum_values on line 10, where it's returned to the calling code (i.e. line 12, to be printed). So, as you see, we work with smaller and smaller sequences, each time building up the result a bit more.