1

I tried below piece of code:

def split(arr,i=0):

    if i==0:
        print("hey")
        splitted=[]
        print('splitted initialized')


    a1=arr[:len(arr)//2]
    a2=arr[len(arr)//2:]
    if len(a1)>2:
        print("splitting "+str(a1))
        i+=1
        split(a1,i)
    else:
        print("not splitting "+str(a1))
        splitted.append(a1)

    if len(a2)>2:
        print("splitting "+str(a2))
        i+=1
        split(a2,i)
    else:
        print("not splitting "+str(a2))
        splitted.append(a2)

    return(splitted)

I am getting the below error when I execute:

split([1,2,3,4,6,7,8,54,76,3,4,5,67,78,8,7,45,2]) I expected the empty list "splitted" to be initializes only once during 0th initialization

hey
splitted initialized
splitting [1, 2, 3, 4, 6, 7, 8, 54, 76]
splitting [1, 2, 3, 4]
not splitting [1, 2]
Traceback (most recent call last):
  File "<pyshell#37>", line 1, in <module>
    split([1,2,3,4,6,7,8,54,76,3,4,5,67,78,8,7,45,2])
  File "\Documents\python_projects-20170821\python_projects\sorting_algorithms\merge_sort\merge_sort.py", line 15, in split
    split(a1,i)
  File "\Documents\python_projects-20170821\python_projects\sorting_algorithms\merge_sort\merge_sort.py", line 15, in split
    split(a1,i)
  File "\Documents\python_projects-20170821\python_projects\sorting_algorithms\merge_sort\merge_sort.py", line 18, in split
    splitted.append(a1)
UnboundLocalError: local variable 'splitted' referenced before assignment

I am able to overcome by nesting the this function within another function as shown below:

below code works fine on calling: splitter([1,2,3,4,6,7,8,54,76,3,4,5,67,78,8,7,45,2])

def splitter(arr):
    splitted=[]
    def split(arr):
        a1=arr[:len(arr)//2]
        a2=arr[len(arr)//2:]
        if len(a1)>2:
            print("splitting "+str(a1))

            split(a1)
        else:
            print("not splitting "+str(a1))
            splitted.append(a1)

        if len(a2)>2:
            print("splitting "+str(a2))

            split(a2)
        else:
            print("not splitting "+str(a2))
            splitted.append(a2)

        return(splitted)
    return split(arr)

I just want to understand why my first version of code dosen't work?

Improve this question
5
  • 2
    In the recursive cases, i is greater than zero and so split() will not define splitted and so you get your error. Commented Jan 31, 2018 at 13:58
  • Actually your nested function solution is a brilliant piece of python design! Commented Jan 31, 2018 at 13:59
  • hi @quamrana but in output you can see hey splitted initialized Commented Jan 31, 2018 at 14:02
  • 1
    @SudhanNadar yes that is correct for the base case i=0 not for every other case in the recursive call Commented Jan 31, 2018 at 14:04
  • Just because in one call to split it defines splitted, does not mean that all recursive calls can see splitted. Commented Jan 31, 2018 at 14:05

4 Answers 4

Reset to default
1

This version of split might work (But I like your nested function better)

def split(arr, splitted=None):

    if splitted == None:
        print("hey")
        splitted = []
        print('splitted initialized')

    a1=arr[:len(arr)//2]
    a2=arr[len(arr)//2:]
    if len(a1)>2:
        print("splitting "+str(a1))
        split(a1, splitted)

    # the reset elided

Note how splitted is passed down the chain of recursion.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Agreed. just curious what happens to the variable splitted.
It may be local to that one instance of function call.
I always dodged these issues in most practical problems but it nags me what if i want to make a decision based based on depth of recursion.
You just need to do some research on recursive functions to find out how parameters are handled.
0

That's because you only define splitted when i is greater than zero. You could try 

def split(arr,splitted=None):

    if splitted is None:
        print("hey")
        splitted=[]
        print('splitted initialized')

and then, when you call your function, you pass the splitted list instead of the parameter i.

Improve this answer

1 Comment

splitted is defined when i is equal to 0.
0 
def split(arr,res,i=0):

    if i==0:
        print("hey")
        print('splitted initialized')


    a1=arr[:len(arr)//2]
    a2=arr[len(arr)//2:]
    if len(a1)>2:
        print("splitting "+str(a1))
        i+=1
        split(a1,res,i)
    else:
        print("not splitting "+str(a1))
        res.append(a1)

    if len(a2)>2:
        print("splitting "+str(a2))
        i+=1
        split(a2,res,i)
    else:
        print("not splitting "+str(a2))
        res.append(a2)

    return

Then the output becomes

a=list()
split([1,2,3,4,6,7,8,54,76,3,4,5,67,78,8,7,45,2],a)
print(a)
Improve this answer

7 Comments

As a programmer you should try very, very, very hard not to use globals.
Also, every time in main after the first call to split you will have to manually reset the result using splitted = []
Sure, but since this is DFS, why do we need to reset the result?
Please tell me what DFS is?
My bad. I meant "depth-first-search". When we are recursing in depth-first mechanism, we will always get the left most entry in the list and they would be appended to the result array, right?
|
0

Here's another way to attack the problem. We start with a helper, cut_at_index which takes a list, an index i, and lambda which will receive the left and right result of the "cut"

Now let's plan how we will write the recursive split function

  • the base case is len(ls) < 3: where we return a singleton list of the unmodified input
  • the inductive case is length is not less than 3 (ie >= 3), therefore we have an array big enough to cut. We call our cut_at_index which gives us new left and right pieces in our lambda. We then call split on each piece and simply merge (+) the result together

As a result of this implementation, pain and suffering are removed from the program

def cut_at_index (ls, i = 0, k = lambda left, right: (left, right)):
  return k (ls[:i], ls[i:])

def split (ls):
  if len (ls) < 3:
    return [ ls ]
  else:
    return cut_at_index (ls, len (ls) // 2, lambda left, right:
      split (left) + split (right))

print (split ([ 1 ]))
print (split ([ 1, 2 ]))
print (split ([ 1, 2, 4 ]))
print (split ([ 1, 2, 3, 4 ]))
print (split ([ 1, 2, 3, 4, 5 ]))
print (split ([ 1, 2, 3, 4, 5, 6 ]))
print (split ([ 1, 2, 3, 4, 5, 6, 8 ]))
print (split ([ 1, 2, 3, 4, 5, 6, 8, 9 ]))
print (split ([ 1, 2, 3, 4, 5, 6, 8, 9, 10 ]))
print (split ([ 1, 2, 3, 4, 5, 6, 8, 9, 10, 11 ]))
print (split ([ 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12 ]))
# [[1]]
# [[1, 2]]
# [[1], [2, 4]]
# [[1, 2], [3, 4]]
# [[1, 2], [3], [4, 5]]
# [[1], [2, 3], [4], [5, 6]]
# [[1], [2, 3], [4, 5], [6, 8]]
# [[1, 2], [3, 4], [5, 6], [8, 9]]
# [[1, 2], [3, 4], [5, 6], [8], [9, 10]]
# [[1, 2], [3], [4, 5], [6, 8], [9], [10, 11]]
# [[1, 2], [3], [4, 5], [6], [8, 9], [10], [11, 12]]

Because cut_at_index's continuation parameter k has a default value, we can also use it in direct style with destructuring assignment (instead of continuation passing style). Program readability is improved as a result.

def split (ls):
  if len (ls) < 3:
    return [ ls ]
  else:
    (left, right) = cut_at_index (ls, len (ls) // 2)
    return split (left) + split (right)

print (split ([ 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12 ]))
# [[1, 2], [3], [4, 5], [6], [8, 9], [10], [11, 12]]
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.