Python list recursive changes

Question

I have a bug in my attempt to add to a list a sequence of numbers recursively. E.g. if the input is [5,3,9], I do [5+1,3+2,9+3] and output [6,5,12]. I want to do this recursively so the way I'm doing it is going through and adding one to a smaller and smaller part of the list as below:

def add_position_recur(lst, number_from=0):
    length = len(lst)
    # base case
    if (length <= 1):
        lst = [x+1 for x in lst]
        print "last is", lst
    else:
        lst = [x+1 for x in lst]
        print "current list is", lst
        add_position_recur(lst[1:], number_from)
        return lst

The problem, though, is that all this does is add 1 to every element of the list. Where is the bug? Is it to do with the way I return the list in the base case?

what is number_from used for? it has zero use in your code. And be aware that you are changing your lst to reference a new list when you do lst = .... It doesn't change the original list passed in as the argument — logee
– logee, Commented Sep 11, 2015 at 2:47

AChampion · Accepted Answer · 2015-09-11 03:03:40Z

When you recurse down your call stack you slice lst which creates a new list, this is not the same as what you return, so you will only ever return the changes you've applied to your list in the first call to the function, losing all changes further down the stack:

>>> add_position_recur([1,2,3])
[2, 3, 4]

This should have returned [2, 4, 6].
You need to consider reassembling the list on the way out to get the changes.

return [lst[0]] + add_position_recur(lst[1:], number_from)

and you need to return lst in your base case:

def add_position_recur(lst, number_from=0):
    length = len(lst)
    # base case
    if (length <= 1):
        lst = [x+1 for x in lst]
        return lst
    else:
        lst = [x+1 for x in lst]
        return [lst[0]] + add_position_recur(lst[1:], number_from)
>>> add_position_recur([1,2,3])
[2, 4, 6]

However, this is quite a complicated approach to this recursion. It is idiomatic for the base case to be the empty list, otherwise take the head and recurse down the tail. So something to consider which uses the number_from:

def add_position_recur(lst, number_from=1):
    if not lst:
        return lst
    return [lst[0]+number_from] + add_position_recur(lst[1:], number_from+1)

>>> add_position_recur([1,2,3])
[2, 4, 6]

This also has the advantage(?) of not changing the passed in lst

slickster · Accepted Answer · 2015-09-11 02:56:05Z

0

Why don't you instead do something like this:

def func(lon, after=[]):
    if not l:
        pass
    else:
        v = len(lon) + lon[-1]
        after.append(v)
        func(lon[:-1], after)
        return after[::-1]

The output of the function for the example you provided matches what you want.

answered Sep 11, 2015 at 2:56

slickster

316 bronze badges

Comments

ejg · Accepted Answer · 2015-09-11 03:08:37Z

0

Currently, you are simply adding 1 to each value of your list.

lst = [x+1 for x in lst]

Rather, you should be increasing a variable which is being added to x with each iteration of x in lst.

lst = [x+(lst.index(x)+1) for x in lst]

This solution assumes that you want the number being added to x to depend on its position in the list relative to the start of the list, rather than being dependent on the position of x relative to the first element which was >1. Meaning, do you want to add 1 or 3 to the value 2 in the following list? The solution above adds three.

lst = [0.5, 0.1, 2, 3]

answered Sep 11, 2015 at 3:08

ejg

1961 gold badge2 silver badges14 bronze badges

2 Comments

Dan D. Over a year ago

Don't do [x+(lst.index(x)+1) for x in lst], it won't work when there are duplicate items and it is also really slow. Use enumerate: [x+(i+1) for i,x in enumerate(lst)].

lvc Over a year ago

@DanD. even better, use the start argument to enumerate to avoid the extra arithmetic: [x+i for i,x in enumerate(lst, start=1)].

Collectives™ on Stack Overflow

Python list recursive changes

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related