Having trouble with basic recursion in python

Question

I am working through How to Think Like a Computer Scientist, and am currently trying to get a grasp on recursion. I am having trouble on one of the problems, so I am hoping you can help me out.

I am writing a function which finds the recursive minimum of a list, whose elements are integers, lists of integers, lists of lists of integers, etc.

Here is my current version:

def recursive_min(nested_num_list):
    """
      >>> recursive_min([9, [1, 13], 2, 8, 6])
      1
      >>> recursive_min([2, [[100, 1], 90], [10, 13], 8, 6])
      1
      >>> recursive_min([2, [[13, -7], 90], [1, 100], 8, 6])
      -7
      >>> recursive_min([[[-13, 7], 90], 2, [1, 100], 8, 6])
      -13
    """
    min = nested_num_list[0]
    while type(min) == type([]):
        min = min[0]
    for item in nested_num_list:
        if type(item) == type([]):
            recursive_min(item)
        elif item < min:
            min = item
    return min

However, this only works to find the minimum at the top level, so I now my code is not getting in to the depth of the list.

Now, looking at the answers, I know my version should read something like:

def recursive_min(nested_num_list):
    """
      >>> recursive_min([9, [1, 13], 2, 8, 6])
      1
      >>> recursive_min([2, [[100, 1], 90], [10, 13], 8, 6])
      1
      >>> recursive_min([2, [[13, -7], 90], [1, 100], 8, 6])
      -7
      >>> recursive_min([[[-13, 7], 90], 2, [1, 100], 8, 6])
      -13
    """
    min = nested_num_list[0]
    while type(min) == type([]):
        min = min[0]
    for item in nested_num_list:
        if type(item) == type([]):
            min_of_elm = recursive_min(item)
            if min_of_elm < min:
                min = min_of_elm
        elif item < min:
            min = item
    return min

Notice that instead of just executing recursive_min(item), it assigns it to a variable, and compares it to the current min. I don't see why I need to do that, as in my mind, if I execute the entire function over the embedded list, and that is a list of integers, it should then get to the elif statement (rather than the if statement) and properly compare the values.

I know I must be missing something here about recursion. I would really appreciate any insight you might be able to give me to help me understand what makes the second version work but the first version fail.

Thank you!

Not only for readability, it's a long subject: see http://stackoverflow.com/questions/1549801/differences-between-isinstance-and-type-in-python and http://www.canonical.org/~kragen/isinstance/ — rubik, May 15 '12 at 19:28

score 2 · Accepted Answer · edited Nov 26 '13 at 13:22

2

Why would it work? You call the function, and it recurses until it finds the min. Then what does it do? It exits back out of all the recursions in turn, until it gets back to the top level. At that point, what's the value of min? Exactly what it was before you started recursing, because you never captured the return value from the recursive function.

Don't forget that each call of the function has its own local variables, therefore its own local value of min.

edited Nov 26 '13 at 13:22

BenMorel

34,448
50
182
322

answered May 15 '12 at 18:41

Daniel Roseman

588,541
66
880
895

Thanks for your answer. But on that last recursion, when the list is in fact of ints, then shouldn't it enter the elif conditional, and then set min to the item? I am thinking maybe the answer to my question has to do with your last sentence. Does that mean that if I set min equal to something 2 steps in to a recursion, that min will not be set to that once it backs out of that recursive step? – evt May 15 '12 at 19:05
@evt: Yes, that last sentence is key. When you call a function recursively, that function has it's own copy of the local variables, so that any assignments made within the callee do not affect the caller. – Steven Rumbalski May 15 '12 at 19:24

Óscar López · Answer 2 · 2012-05-22T03:44:14.577

There are many ways to solve this problem. Personally, I prefer a more functional approach - using only recursion over the list, with no loops or local variables. It's certainly not the most efficient way to solve the problem, but it's simple and elegant:

def recursive_min(num_list):
    return aux_min(num_list[1:], num_list[0]) if num_list else None

def aux_min(num_list, min_num):
    if not num_list:
        return min_num
    elif not isinstance(num_list, list):
        return min(num_list, min_num)
    else:
        return min(aux_min(num_list[0],  min_num),
                   aux_min(num_list[1:], min_num))

In the above code, the main function is recursive_min, which calls the helper function aux_min. In turn, aux_min receives a list and the current minimum, and splits the problem in three cases:

If the list is empty, return the current minimum
If it's a number and not a list, return the minimum between the number and the current minimum
If it's a list, recursively return the minimum between its first element and the rest of the list

It works for a list of list because in the third case, the first element could be a list itself.

Having trouble with basic recursion in python

2 Answers2