Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

Python

Posted by amandae
amandae
15,727 Points

Not able to access an inner function in python.

Hi. This is from some recursion practice I was doing outside of Treehouse. If this type of question isn't allowed - Mod, please delete with my apologies.

This code is to solve for the "Best Sums." Given a target number and a list of numbers, the goal is to create a list of lists containing only the solutions equal to the shortest solution. Numbers may be used any number of times, and all numbers are positive integers. It uses a dictionary (bs_dict) for memoization in the recursion.

In the code below, the inner function never runs. Unless the target_number is in the num_list, it always returns [] - which is an empty best sums list.

Thanks in advance for any help. I am SO stuck on this one.

def best_sum2(target_number, num_list):
    best_sums = []
    bs_dict = {}
    bs_dict.clear()
    if target_number in num_list:
        return target_number

    def best_sum2_helper():
        if target_number == 0:
            return []

        if target_number in bs_dict.keys():
            return bs_dict[target_number]

        for each_num in num_list:
            new_target = target_number - each_num

            if new_target >= 0:
                new_target_list = best_sum2_helper()

                if new_target_list is not None:
                    new_target_list = new_target_list + [each_num]
                    bs_dict[each_num] = new_target_list

                    min_val = min([len(bs_dict[ele]) for ele in bs_dict])
                    for ele in bs_dict:
                        if len(bs_dict[ele]) == min_val:
                            best_sums.append(ele)

        return best_sum2_helper()

    return best_sums


print(best_sum2(7, [5, 3, 4, 7]))     # 7
print(best_sum2(8, [2, 3, 5]))        # 3,5
print(best_sum2(8, [1, 4, 5]))        # 4,4
print(best_sum2(100, [1, 2, 5, 25]))  # 25,25,25,25

2 Answers

Chris Freeman
MOD
Chris Freeman
Treehouse Moderator 68,426 Points
Chris Freeman
Chris Freeman
Treehouse Moderator 68,426 Points

Hey amandae, looking at the flow after “compressing” best_sum2_helper:

def best_sum2(target_number, num_list):
    best_sums = []
    bs_dict = {}
    bs_dict.clear()
    if target_number in num_list:
        return target_number

    def best_sum2_helper():
        # defined....
        return best_sum2_helper()

    return best_sums

You can now see that there is no call to best_sum2_helper(). If the target_number is in the num_list then it is returned. Otherwise, best_sums (currently empty) is returned.

amandae
amandae
15,727 Points

Thanks, Chris Freeman.

Where would you put the call?
I thought I was calling it when I returned it. I notice now that I did have an extra set of () on the return, but I tried running it without and it still doesn't work.

This article is one of the ones I referenced. The style I used is in the closures section about halfway down. I also tried it without the return statement, with the (), and it returns a recursion depth error. Geeks for Geeks

Thanks, again!

Chris Freeman
Chris Freeman
Treehouse Moderator 68,426 Points
Chris Freeman
Chris Freeman
Treehouse Moderator 68,426 Points

Since line 19 is expecting best_sum2_helper() to return a list, the last line of the best_sum2_helper` function should perhaps be:

return best_sums

Also since the main function is expected to return a list, then the result of the outer call to best_sum2_helper() should be returned.

So it sees you need the structure:

def best_sum2(target_number, num_list):
    best_sums = []
    bs_dict = {}
    bs_dict.clear()
    if target_number in num_list:
        return target_number

    def best_sum2_helper():
        # inner code ...

        return best_sums

    return best_sum2_helper()

As to the issue with recursion error, there seems to be some logic issues:

  • the value of num_list never changes, so each invocation of best_sum2_helper will loop with each_num the same way
  • the value of target_number never changes, so the first new_target value is always the same.

So when each invocation of best_sum2_helper() is run, at line 19 new_target_list = best_sum2_helper() will start a new invocation of best_sum2_helper() with nothing different. This repeats 1000 until the recursion limit is reached.

For example, in best_sum2(8, [2, 3, 5]), the first new_target is 6, since this is >=0, the recursion is called, where the first new_target is 6....

I'll have to leave it to you to fix the algorithm. Good luck!!

amandae
amandae
15,727 Points
amandae
amandae
15,727 Points

Thank you! Chris Freeman.

I really appreciate the help. I'll post back if I ever figure out the answer. Right now, it seems like every time I try to fix one thing, another two break, and I've spent waaayyy too much time on it. Last night I got the recursive problem fixed, and this morning, I thought I had everything else fixed. Then PyCharm told me I'd somehow turned a list into an integer, and it didn't know what to do with it (no strings involved...).
It did occur to me that importing anti-gravity about three quarters of the way through might help, but decided to try just importing magic instead, because it seemed more likely fix than anti-gravity. At that point I figured out magic is actually a thing Python imports, and spent the next half an hour reading about file identification (not to be confused with magic methods)... lol! :)

I'll come back to it in a few days and start over. Hopefully, then it will all just fall together.