Problem with passing evaluated expression to a recursion in Python

Question

I have encountered this problem many times. The idea of the example recursion is to generate all combination of characters by choosing one character of each element from the input array. Here is working example:

def gen_comb(input_arr, result, index, curr_comb):
    if len(curr_comb) == len(input_arr):
        result.append(curr_comb)
        return

    for letter in input_arr[index]:
        gen_comb(input_arr, result, index + 1, curr_comb + letter)

    return result

print(gen_comb(input_arr=['abc', 'def'], result=[], index=0, curr_comb=""))

And here is the output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']. The problem occurs when slightly changing the above code:

def gen_comb(input_arr, result, index, curr_comb):
    if len(curr_comb) == len(input_arr):
        result.append(curr_comb)
        return

    for letter in input_arr[index]:
        curr_comb += letter
        gen_comb(input_arr, result, index + 1, curr_comb)

    return result

The only difference is adding curr_comb += letter outside the method signature. In this case the error is IndexError: list index out of range but there is similar examples with wrong result.

The question is:

What is the difference between passing an expression to a recursive function and calculating the expression before to pass to the function?

curr_comb + letter doesn't modify curr_comb but curr_comb += letter does. — 001
– 001, Commented Sep 1, 2019 at 15:26

wwii · Accepted Answer · 2019-09-01 21:24:05Z

Your function relies on a base case of len(curr_comb) == len(input_arr). In the function instance where the base case is met, execution stops and the for statement doesn't execute. The way you have designed the function you expect the base case to be met at the same time that you have passed an erroneous index.
curr_comb += letter changes the length of curr_comb in the current instance of the function. This is happening within a for loop. When the next function instance returns, this for loop continues iteration and the length of curr_comb continues to increase.
Eventually len(curr_comb) > len(input_arr) and the base case in the next function instance fails, the for statement is evaluated and the code tries to index an item that doesn't exist in input_arr.

You can see this by printing or at http://www.pythontutor.com/visualize.html#mode=edit

That was just a fancy way of restating @JohnnyMopp 's comment to your question.

My answer is specific to your function examples and tries to explain why the second function doesn't work.

What is the difference between passing an expression to a recursive function and calculating the expression before to pass to the function?

A general answer to this might be:
Both are acceptable: BUT

You have to design the base case to match the rest of the function.
You have to understand how your function works.
If you change something in a working recursive function, it is probable that you will have to change something else.

However, the more I think about it I'm starting to wonder if it is a bad idea to change the state of something within a function instance if it is going to continue executing after the next recursive call returns. Seems like you should only alter something for use in the next instance. I don't have enough experience but it is starting to smell fishy. Maybe someone will comment. I certainly don't recall reading any prohibitions against it.

Sam Chats · Accepted Answer · 2019-09-01 15:30:07Z

for letter in input_arr[index]:
        curr_comb += letter
        gen_comb(input_arr, result, index + 1, curr_comb)

Above code is doing an aggregration. So if input_arr[index] is 'abcd', and curr_comb is 'h', the unrolled loop execution will be as follows:

gen_comb(input_arr, result, index+1, 'ha')
gen_comb(input_arr, result, index+1, 'hab')
gen_comb(input_arr, result, index+1, 'habc')
gen_comb(input_arr, result, index+1, 'habcd')

But actually it should've been:

gen_comb(input_arr, result, index+1, 'ha')
gen_comb(input_arr, result, index+1, 'hb')
gen_comb(input_arr, result, index+1, 'hc')
gen_comb(input_arr, result, index+1, 'hd')

Which is the output of the original code:

for letter in input_arr[index]:
        gen_comb(input_arr, result, index + 1, curr_comb + letter)

Collectives™ on Stack Overflow

Problem with passing evaluated expression to a recursion in Python

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related