0

For the following recursive function, I don't know why the output is

[['c']]
[[['c']]]

if the input is a list: 

['a',['b',['c']]]

I thought the output should be 

[['c']]
[['b', ['c']]]

def rec(L):
    if len(L)==1:
        return
    L.pop(0)
    for elem in L:
        rec(elem)
    print L
    return
Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
bcxiao
  • 31
  • 4
  • Can you explain what this code is trying to achieve? – cs95 Mar 13 '18 at 06:11
  • Can you indent your function definition so that Python will accept it. Is it all the lines after the `def`? It looks plausible; you should indent them all by 4 spaces. Python, of all languages, will give you grief if you don't get your indentation correct. – Jonathan Leffler Mar 13 '18 at 06:13
  • I am trying to use recursive function to build a tree from a list. That result is different from what I thought, which causes a bug in my work. – bcxiao Mar 13 '18 at 06:21
  • 1
    Trace through this step by step and it's obvious what's happening (except for the part where you can recurse on a string—which fortunately has length 1, so you never get to the `L.pop(0)`, which would raise a `TypeError`)—but it's not at all obvious why you thought something different should happen. – abarnert Mar 13 '18 at 06:21
  • 1
    Do you know how to use `pdb`? If not, this is a great time to learn. If you don't want to learn that, just add a bunch of `print` statements (although you may want to either pass down a "depth" argument, or use frame hackery to get one on the fly, so you can indent things in a readable way). – abarnert Mar 13 '18 at 06:22

1 Answers1

2

Lists are passed by reference. List elements will also be passed by reference if they themselves are lists also.

In the first level of recursion you remove the first element (a) of L and pass the new first element ([b,[c]]) to the second level of recursion under the name of elem. Any changes made to elem will be also made to the first element of L meaning by the time you get to your print statement in the most outer recursion that first element has already been reduced to [[c]].

Ross Batten
  • 114
  • 8
  • Thanks a lot for your answer. Do you know how to change the code to get the result I want? – bcxiao Mar 13 '18 at 06:37
  • I think using deepcopy is one solution. – bcxiao Mar 13 '18 at 06:48
  • Sure, just pass elem[:] instead of elem and it will create a copy instead of passing by reference. If you don't like that one there's a number of different ways to copy an array here: https://stackoverflow.com/questions/2612802/how-to-clone-or-copy-a-list – Ross Batten Mar 13 '18 at 06:53