Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #46447 > unrolled thread

Can anyone please help me in understanding the following python code

Back to article view | Back to comp.lang.python

Contents

  Can anyone please help me in understanding the following python code bhk755@gmail.com - 2013-05-30 02:48 -0700
    Re: Can anyone please help me in understanding the following python code Chris Angelico <rosuav@gmail.com> - 2013-05-30 20:01 +1000
    Re: Can anyone please help me in understanding the following python code Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de> - 2013-05-30 10:17 +0000
    Re: Can anyone please help me in understanding the following python code bhk755@gmail.com - 2013-05-30 03:19 -0700
      Re: Can anyone please help me in understanding the following python	code Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de> - 2013-05-30 10:43 +0000
      Re: Can anyone please help me in understanding the following python code Chris Angelico <rosuav@gmail.com> - 2013-05-30 20:47 +1000
      Re: Can anyone please help me in understanding the following python code Joshua Landau <joshua.landau.ws@gmail.com> - 2013-05-30 12:11 +0100
    Re: Can anyone please help me in understanding the following python code Joshua Landau <joshua.landau.ws@gmail.com> - 2013-05-30 12:03 +0100
    Re: Can anyone please help me in understanding the following python code bhk755@gmail.com - 2013-05-30 05:39 -0700
      Re: Can anyone please help me in understanding the following python code bhk755@gmail.com - 2013-05-30 05:42 -0700
        Re: Can anyone please help me in understanding the following python code Dave Angel <davea@davea.name> - 2013-05-30 09:29 -0400
      Re: Can anyone please help me in understanding the following python code bhk755@gmail.com - 2013-05-30 05:42 -0700
      Re: Can anyone please help me in understanding the following python code Chris Angelico <rosuav@gmail.com> - 2013-05-30 22:55 +1000
    Re: Can anyone please help me in understanding the following python code bhk755@gmail.com - 2013-05-30 06:01 -0700
    Re: Can anyone please help me in understanding the following python code bhk755@gmail.com - 2013-05-30 21:53 -0700
    Re: Can anyone please help me in understanding the following python code bhk755@gmail.com - 2013-05-30 21:54 -0700
      Re: Can anyone please help me in understanding the following python code Cameron Simpson <cs@zip.com.au> - 2013-05-31 15:43 +1000
      Re: Can anyone please help me in understanding the following python code Chris Angelico <rosuav@gmail.com> - 2013-05-31 17:13 +1000
    Re: Can anyone please help me in understanding the following python code rusi <rustompmody@gmail.com> - 2013-06-01 10:43 -0700

#46447 — Can anyone please help me in understanding the following python code

Code :
-----
def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i<len(lefthalf) and j<len(righthalf):
            if lefthalf[i]<righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i<len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j<len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

Output:
-------
('Splitting ', [54, 26, 93, 17, 77, 31, 44, 55, 20])
('Splitting ', [54, 26, 93, 17])
('Splitting ', [54, 26])
('Splitting ', [54])
('Merging ', [54])
('Splitting ', [26])
('Merging ', [26])
('Merging ', [26, 54])
('Splitting ', [93, 17])
('Splitting ', [93])
('Merging ', [93])
('Splitting ', [17])
('Merging ', [17])
('Merging ', [17, 93])
('Merging ', [17, 26, 54, 93])
('Splitting ', [77, 31, 44, 55, 20])
('Splitting ', [77, 31])
('Splitting ', [77])
('Merging ', [77])
('Splitting ', [31])
('Merging ', [31])
('Merging ', [31, 77])
('Splitting ', [44, 55, 20])
('Splitting ', [44])
('Merging ', [44])
('Splitting ', [55, 20])
('Splitting ', [55])
('Merging ', [55])
('Splitting ', [20])
('Merging ', [20])
('Merging ', [20, 55])
('Merging ', [20, 44, 55])
('Merging ', [20, 31, 44, 55, 77])
('Merging ', [17, 20, 26, 31, 44, 54, 55, 77, 93])
[17, 20, 26, 31, 44, 54, 55, 77, 93]


Question:
---------
Function mergeSort is called only once, but it is getting recursively executed after the printing the last statement "print("Merging ",alist)". But don't recursion taking place except at these places "mergeSort(lefthalf), mergeSort(righthalf)"

Sometimes the function execution directly starts from i=0,j=0,k=0 . Not sure how.

Can anyone please help me out here?

[toc] | [next] | [standalone]

#46448

On Thu, May 30, 2013 at 7:48 PM,  <bhk755@gmail.com> wrote:
> Function mergeSort is called only once, but it is getting recursively executed after the printing the last statement "print("Merging ",alist)". But don't recursion taking place except at these places "mergeSort(lefthalf), mergeSort(righthalf)"
>
> Sometimes the function execution directly starts from i=0,j=0,k=0 . Not sure how.

When it says "Splitting" with a single-element list, it then
immediately prints "Merging" and returns (because all the rest of the
code is guarded by the 'if'). Execution then continues where it left
off, in the parent.

One good way to get an idea of what's going on is to add a recursion
depth parameter. Keep all the rest of the code the same, but change
the print and recursion lines to be like this:

def mergeSort(alist,depth):
    print("%*cSplitting %r"%(depth*2,' ',alist))
    # ...
        mergeSort(lefthalf,depth+1)
        mergeSort(righthalf,depth+1)
    # ...
    print("%*cMerging %r"%(depth*2,' ',alist))

mergeSort(alist,0)

That'll indent everything according to the depth of the call stack.
(Also, I changed your 'print's to be compatible with Python 2 and
Python 3; you seemed to have Python 3 style function calls and a
Python 2 interpreter.) Hopefully that'll make clearer what's going on!

ChrisA

[toc] | [prev] | [next] | [standalone]

#46449

 <bhk755 <at> gmail.com> writes:
>
> 
> Function mergeSort is called only once, but it is getting recursively
executed after the printing the last
> statement "print("Merging ",alist)". But don't recursion taking place
except at these places
> "mergeSort(lefthalf), mergeSort(righthalf)"
> 
> Sometimes the function execution directly starts from i=0,j=0,k=0 . Not
sure how.

Maybe you should tell us first what output you would have expected.
It's not really clear from your question what confuses you. Doesn't the
algorithm do what it's supposed to do? When does the function start from
i=0, j=0, k=0 ? What exactly is the output then ?
Maybe you are confused by the fact that the algorithm is recursive twice. It
first goes through the lefthand branch, then only on its way out it works on
the righthand branch. So the recursion through mergeSort is not started only
once as you say, but twice (after finishing the recursion through
mergeSort(lefthand), another recursion is kicked off by calling
mergeSort(righthand).
Best,
Wolfgang

[toc] | [prev] | [next] | [standalone]

#46450

Thanks for the reply Chris.

I am newbie to python, so please excuse me if I am asking chilly questions.

Can you please explain more about the following sentence.
"When it says "Splitting" with a single-element list, it then 
immediately prints "Merging" and returns (because all the rest of the 
code is guarded by the 'if'). Execution then continues where it left 
off, in the parent."

Because I am not sure how the control can go back to top of the function unless  there is no loops there.

Also, Can you please let me know how did you found out that I am using Python 2 Interpreter.


Bharath

[toc] | [prev] | [next] | [standalone]

#46451 — Re: Can anyone please help me in understanding the following python code

 <bhk755 <at> gmail.com> writes:

> 
> Thanks for the reply Chris.
> 
> I am newbie to python, so please excuse me if I am asking chilly questions.
> 
> Can you please explain more about the following sentence.
> "When it says "Splitting" with a single-element list, it then 
> immediately prints "Merging" and returns (because all the rest of the 
> code is guarded by the 'if'). Execution then continues where it left 
> off, in the parent."
> 
> Because I am not sure how the control can go back to top of the function
unless  there is no loops there.
>

It doesn't. The function simply returns and execution resumes in the parent,
i.e. in the calling function at depth-1, where it left off. In Python, a
return None is implied when a function falls off its end.

> Also, Can you please let me know how did you found out that I am using
Python 2 Interpreter.

print as a statement (without parentheses) only works in Python 2, in Python
3 print is a function.

> 
> Bharath
> 
> 

[toc] | [prev] | [next] | [standalone]

#46452

On Thu, May 30, 2013 at 8:19 PM,  <bhk755@gmail.com> wrote:
> Thanks for the reply Chris.
>
> I am newbie to python, so please excuse me if I am asking chilly questions.

All questions are welcome!

> Can you please explain more about the following sentence.
> "When it says "Splitting" with a single-element list, it then
> immediately prints "Merging" and returns (because all the rest of the
> code is guarded by the 'if'). Execution then continues where it left
> off, in the parent."

The code goes like this:

1) Print "Splitting"
2) If there's more than one element in the list:
2a) Divide the list in half
2b) Call self on each half
2c) Merge
3) Print "Merging

In step 2b, all the steps from 1 through 3 are executed again (twice).
Soon, those calls will just output "Splitting" followed by "Merging";
and then we go back to 2c. That's why it *seems* that the code goes
from 3 to 2c. You'll notice that the call depth decreases when this
happens.

> Because I am not sure how the control can go back to top of the function unless  there is no loops there.
>
> Also, Can you please let me know how did you found out that I am using Python 2 Interpreter.

That one is actually based on my crystal ball. Here on python-list, we
issue them to all our top respondents; they're extremely useful. I'll
let you in on part of the secret of how this works, though.

In Python 2, 'print' is (by default) a statement. When you give it
something in parentheses, it sees a tuple:

print("Splitting ",alist)
('Splitting ', [54, 26, 93, 17, 77, 31, 44, 55, 20])

In Python 3, 'print' is a function. It takes arguments, and prints out
each argument, separated by spaces.

print("Splitting ",alist)
Splitting  [17, 20, 26, 31, 44, 54, 55, 77, 93]

You can make Python 2 behave the same way by putting this at the top
of your program:

from __future__ import print_function

ChrisA

[toc] | [prev] | [next] | [standalone]

#46456

On 30 May 2013 11:19,  <bhk755@gmail.com> wrote:
> Also, Can you please let me know how did you found out that I am using Python 2 Interpreter.

Do you have access to a Python3 interpreter? If so, try running it and
your output will look like:

Splitting  [54, 26, 93, 17, 77, 31, 44, 55, 20]
Splitting  [54, 26, 93, 17]
Splitting  [54, 26]
Splitting  [54]
Merging  [54]
Splitting  [26]
Merging  [26]
... BLAH BLAH BLAH

Which is obviously much nicer. This is how Chris knew the code was
written for Python3. Therefore I would suggest you use Python3 - not
all code runs on both!

The "proper" way to write the prints for Python2 is without the brackets:

print "Merging ",alist

But the methods Chris and I have used work the same on both so are
probably better in this case. They're more complicated, though.

[toc] | [prev] | [next] | [standalone]

#46455

On 30 May 2013 10:48,  <bhk755@gmail.com> wrote:
> Question:
> ---------
> Function mergeSort is called only once, but it is getting recursively executed after the printing the last statement "print("Merging ",alist)". But don't recursion taking place except at these places "mergeSort(lefthalf), mergeSort(righthalf)"
>
> Sometimes the function execution directly starts from i=0,j=0,k=0 . Not sure how.

Here's some different code; it does the same thing but in a less weird way:

##########################
def mergeSort(alist, depth=1):
    # If the piece we have to sort is [i] or [], then we have no sorting to do
    if len(alist) <= 1:
        # Returning what we were given
        # Make a new list from it, though, because we are nice
        print("{padding}return {list}\n".format(padding=" "*depth*8,
list=alist))
        return alist[:]

    # Split along the middle
    mid = len(alist)//2

    # We have two halves
    lefthalf = alist[:mid]
    righthalf = alist[mid:]

    # Which we sort, so we have two sorted halves
    print("{padding}lefthalf  = mergesort({list})\n".format(padding="
"*depth*8, list=lefthalf))
    lefthalf  = mergeSort(lefthalf,  depth+1)

    print("{padding}righthalf = mergesort({list})\n".format(padding="
"*depth*8, list=righthalf))
    righthalf = mergeSort(righthalf, depth+1)


    # We want to return a sorted "alist" from our two lists
    # We'll add the items to here
    new_list = []

    # We'll go through adding the smallest to new_list
    while lefthalf and righthalf:

        # Lefthalf has the smaller item, so we "pop" it off into new_list
        if lefthalf[0] < righthalf[0]:
            new_list.append(lefthalf.pop(0))

        # Righthalf has the smaller item, so we "pop" it off into new_list
        else:
            new_list.append(righthalf.pop(0))

    # One of our lists isn't empty, so just add them on
    new_list += lefthalf + righthalf

    print("{padding}return {list}\n".format(padding=" "*depth*8, list=new_list))
    return new_list

print("Start mergesort({list}):\n".format(list=[2, 4, 0, 1]))

sorted_list = mergeSort([2, 4, 0, 1])

print("Our final result: {list}".format(list=sorted_list))
##########################

And it gives

##########################
Start mergesort([2, 4, 0, 1]):

        lefthalf  = mergesort([2, 4])

                lefthalf  = mergesort([2])

                        return [2]

                righthalf = mergesort([4])

                        return [4]

                return [2, 4]

        righthalf = mergesort([0, 1])

                lefthalf  = mergesort([0])

                        return [0]

                righthalf = mergesort([1])

                        return [1]

                return [0, 1]

        return [0, 1, 2, 4]

Our final result: [0, 1, 2, 4]
##########################

Hopefully this code is a little easier to understand - the original
changes the list while it is running the algorithm and mine makes new
lists. The algorithm is very similar, and what you learn applies to
both.

You can see in the output (thanks Chris Angelico) that the main
function is always running. It runs *two* other instances: lefthalf
and righthalf.

So the "mergesort([2, 4, 0, 1])" runs "lefthalf  = mergesort([2, 4])"

"mergesort([2, 4])" runs "lefthalf  = mergesort([2])"

"mergesort([2])" gives back [2] to "mergesort([2, 4])"

"mergesort([2, 4])" goes "OH! I can continue now" and runs "righthalf
= mergesort([4])"

"mergesort([4])" gives back [4] to "mergesort([2, 4])"

"mergesort([2, 4])" goes "OH! I can continue now" and gives back [2,
4] to "mergesort([2, 4, 0, 1])"

"mergesort([2, 4, 0, 1])" goes "OH! I can continue now" and runs
"righthalf = mergesort([0, 1])"

"mergesort([0, 1])" runs "lefthalf  = mergesort([0])"

"mergesort([0])" gives back [0] to "mergesort([0, 1])"

"mergesort([0, 1])" goes "OH! I can continue now" and runs "righthalf
= mergesort([1])"

"mergesort([1])" gives back [1] to "mergesort([0, 1])"

"mergesort([0, 1])" goes "OH! I can continue now" and gives back [0,
1] to "mergesort([2, 4, 0, 1])"

"mergesort([2, 4, 0, 1])" goes "OH! I can continue now" and gives back
[0, 1, 2, 4]

DONE.

Does that help you see the flow?



Exactly the same flow happens for your code. The difference is that
instead of returning a list, mergesort *sorts* a list, and then that
is used to replace items in the original list. Personally, their way
is a little silly (and mine is inefficient, so use neither).


Question: Why did you rewrite the code?
Answer: Revising is boring.


Question: Sometimes the function execution directly starts from
i=0,j=0,k=0 . Not sure how.
Answer: That's not a question. Anyhow:

i, j and k are LOCAL to a function. "mergesort([2, 4, 0, 1])" has a
different i, j and k than "mergesort([0, 1])", They never use each
other's i, j and k. Hence for each recursion they run "i=0, j=0, k=0"
and they are set to 0 within the function.


Does this help?

[toc] | [prev] | [next] | [standalone]

#46475

Thanks Chris, Wolfgang and Joshua for your replies.

---
In step 2b, all the steps from 1 through 3 are executed again (twice). 
Soon, those calls will just output "Splitting" followed by "Merging"; 
and then we go back to 2c. That's why it *seems* that the code goes 
from 3 to 2c. You'll notice that the call depth decreases when this 
happens

Chris, Can you please let me know what makes the control of the program code go to  2c after the output "Merging". 

Also, please look into the following output, 



 before calling main mergesort

 Splitting [54, 26, 93, 17, 77, 31, 44, 55, 20]
left half before split  [54, 26, 93, 17]
right half before split [77, 31, 44, 55, 20]
  Splitting [54, 26, 93, 17]
left half before split  [54, 26]
right half before split [93, 17]
    Splitting [54, 26]
left half before split  [54]
right half before split [26]
      Splitting [54]
      Merging [54]
      Splitting [26]
      Merging [26]

HERE AFTER SPLIT

left half after split [54]
right half after split [26]
    Merging [26, 54]
    Splitting [93, 17]
left half before split  [93]
right half before split [17]
      Splitting [93]
      Merging [93]
      Splitting [17]
      Merging [17]

HERE AFTER SPLIT

left half after split [93]
right half after split [17]
    Merging [17, 93]

HERE AFTER SPLIT

left half after split [26, 54]
right half after split [17, 93]
  Merging [17, 26, 54, 93]
  Splitting [77, 31, 44, 55, 20]
left half before split  [77, 31]
right half before split [44, 55, 20]
    Splitting [77, 31]
left half before split  [77]
right half before split [31]
      Splitting [77]
      Merging [77]
      Splitting [31]
      Merging [31]

HERE AFTER SPLIT

left half after split [77]
right half after split [31]
    Merging [31, 77]
    Splitting [44, 55, 20]
left half before split  [44]
right half before split [55, 20]
      Splitting [44]
      Merging [44]
      Splitting [55, 20]
left half before split  [55]
right half before split [20]
        Splitting [55]
        Merging [55]
        Splitting [20]
        Merging [20]

HERE AFTER SPLIT

left half after split [55]
right half after split [20]
      Merging [20, 55]

HERE AFTER SPLIT

left half after split [44]
right half after split [20, 55]
    Merging [20, 44, 55]

HERE AFTER SPLIT

left half after split [31, 77]
right half after split [20, 44, 55]
  Merging [20, 31, 44, 55, 77]

HERE AFTER SPLIT

left half after split [17, 26, 54, 93]
right half after split [20, 31, 44, 55, 77]
 Merging [17, 20, 26, 31, 44, 54, 55, 77, 93]

 after calling main mergesort

[17, 20, 26, 31, 44, 54, 55, 77, 93]

-----------------------------

In the above output, the control goes to "HERE AFTER SPLIT" after the "Merging" statement which is of-course the last statement in the function.On what condition this is happening.
Ideally as per my understanding, after the last statement of a function the control should come out of the function. 
Please correct me if I am wrong here.
There is something with respect-to functions in python that I am not able to understand.

[toc] | [prev] | [next] | [standalone]

#46477

On Thursday, May 30, 2013 6:09:20 PM UTC+5:30, bhk...@gmail.com wrote:
> Thanks Chris, Wolfgang and Joshua for your replies.
> 
> 
> 
> ---
> 
> In step 2b, all the steps from 1 through 3 are executed again (twice). 
> 
> Soon, those calls will just output "Splitting" followed by "Merging"; 
> 
> and then we go back to 2c. That's why it *seems* that the code goes 
> 
> from 3 to 2c. You'll notice that the call depth decreases when this 
> 
> happens
> 
> 
> 
> Chris, Can you please let me know what makes the control of the program code go to  2c after the output "Merging". 
> 
> Also, please look into the following output for the same program with more print statements, 
> ---------------------------------------------- 
>  before calling main mergesort 
> 
>  Splitting [54, 26, 93, 17, 77, 31, 44, 55, 20]
> 
> left half before split  [54, 26, 93, 17]
> 
> right half before split [77, 31, 44, 55, 20]
> 
>   Splitting [54, 26, 93, 17]
> 
> left half before split  [54, 26]
> 
> right half before split [93, 17]
> 
>     Splitting [54, 26]
> 
> left half before split  [54]
> 
> right half before split [26]
> 
>       Splitting [54]
> 
>       Merging [54]
> 
>       Splitting [26]
> 
>       Merging [26]
> 
> 
> 
> HERE AFTER SPLIT
> 
> 
> 
> left half after split [54]
> 
> right half after split [26]
> 
>     Merging [26, 54]
> 
>     Splitting [93, 17]
> 
> left half before split  [93]
> 
> right half before split [17]
> 
>       Splitting [93]
> 
>       Merging [93]
> 
>       Splitting [17]
> 
>       Merging [17]
> 
> 
> 
> HERE AFTER SPLIT
> 
> 
> 
> left half after split [93]
> 
> right half after split [17]
> 
>     Merging [17, 93]
> 
> 
> 
> HERE AFTER SPLIT
> 
> 
> 
> left half after split [26, 54]
> 
> right half after split [17, 93]
> 
>   Merging [17, 26, 54, 93]
> 
>   Splitting [77, 31, 44, 55, 20]
> 
> left half before split  [77, 31]
> 
> right half before split [44, 55, 20]
> 
>     Splitting [77, 31]
> 
> left half before split  [77]
> 
> right half before split [31]
> 
>       Splitting [77]
> 
>       Merging [77]
> 
>       Splitting [31]
> 
>       Merging [31]
> 
> 
> 
> HERE AFTER SPLIT
> 
> 
> 
> left half after split [77]
> 
> right half after split [31]
> 
>     Merging [31, 77]
> 
>     Splitting [44, 55, 20]
> 
> left half before split  [44]
> 
> right half before split [55, 20]
> 
>       Splitting [44]
> 
>       Merging [44]
> 
>       Splitting [55, 20]
> 
> left half before split  [55]
> 
> right half before split [20]
> 
>         Splitting [55]
> 
>         Merging [55]
> 
>         Splitting [20]
> 
>         Merging [20]
> 
> 
> 
> HERE AFTER SPLIT
> 
> 
> 
> left half after split [55]
> 
> right half after split [20]
> 
>       Merging [20, 55]
> 
> 
> 
> HERE AFTER SPLIT
> 
> 
> 
> left half after split [44]
> 
> right half after split [20, 55]
> 
>     Merging [20, 44, 55]
> 
> 
> 
> HERE AFTER SPLIT
> 
> 
> 
> left half after split [31, 77]
> 
> right half after split [20, 44, 55]
> 
>   Merging [20, 31, 44, 55, 77]
> 
> 
> 
> HERE AFTER SPLIT
> 
> 
> 
> left half after split [17, 26, 54, 93]
> 
> right half after split [20, 31, 44, 55, 77]
> 
>  Merging [17, 20, 26, 31, 44, 54, 55, 77, 93]
> 
> 
> 
>  after calling main mergesort
> 
> 
> 
> [17, 20, 26, 31, 44, 54, 55, 77, 93]
> 
> -------------------------------------------------------
>  
> In the above output, the control goes to "HERE AFTER SPLIT" after the "Merging" statement which is of-course the last statement in the function.On what condition this is happening.
> 
> Ideally as per my understanding, after the last statement of a function the control should come out of the function. 
> 
> Please correct me if I am wrong here.
> 
> There is something with respect-to functions in python that I am not able to understand.

[toc] | [prev] | [next] | [standalone]

#46490

On 05/30/2013 08:42 AM, bhk755@gmail.com wrote:

     <SNIP lots of double-spaced googlegroups nonsense.  Please read
              this http://wiki.python.org/moin/GoogleGroupsPython  >


>>
>> In the above output, the control goes to "HERE AFTER SPLIT" after the "Merging" statement which is of-course the last statement in the function.On what condition this is happening.
>>
>> Ideally as per my understanding, after the last statement of a function the control should come out of the function.
>>
>> Please correct me if I am wrong here.
>>
>> There is something with respect-to functions in python that I am not able to understand.
>

I think you misunderstand recursion.  And you should study it in a 
simpler example before trying to tackle that sort function.

After the last statement of a function, or after an explicit return 
statement, the function does indeed return control to whoever called it. 
  And if the call was in the middle of some other function, that's the 
place where execution will continue.  Functions may nest this way to 
pretty large depths of complexity.

If you're not sure you understand that, we should stop here.  So in your 
reply, tell me if you can readily grasp function dfunc() calling 
cfunc(), which calls bfunc(), which calls afunc().  When afunc() 
returns, you'll be right in the middle of bfunc(), right after the call 
was made.

Now to recursion.  One can write a function which solves a particular 
problem by doing some of the work, but by calling on other functions 
which solve simpler subproblems.  Recursion comes in when those other 
functions are simply instances of the same one.  So instead of dfunc() 
calling cfunc(), we have rfunc() calling rfunc() calling rfunc() calling 
rfunc().

Let's take a classic problem for explaining recursion:  factorial.

We can write a simple function that solves the problem for 0:

def afunc(n):
     if n == 0:
          return 1
     else:
          throw-some-exception

Silly function, I know.  Now let's write one that solves it for one.

def bfunc(n):
     if n == 1:
          return 1 * afunc(n-1)
     else:
          throw-some-exception

Now for two:

def bfunc(n):
     if n == 2:
          return 2 * bfunc(n-1)
     else:
          throw-some-exception


Notice that each function calls the one above it to solve the "simpler" 
problem.  Now if we wanted this to work for n=100, it would get really 
tedious.  So let's see if we can write one function that handles all of 
these cases.

def rfunc(n):
     if n == 0:
         return 1
     else:
         return n * rfunc(n-1)

Now if we call this with n==3, it'll make the zero check, then it'll 
call another function with the value 2.  that one will in turn call 
another function with the value 1.  And so on.  So this function calls 
itself, as we say recursively.

Now, for this simple case, we could have used a simple loop, or just 
called the library function.  But it's a simple enough example to follow 
in its entirety (if I've been clear in my writing).

Your mergeSort() function calls itself recursively, and each time it 
does, it passes a *smaller* list to be sorted.  Eventually the calls 
recurse down to a list of size 1, which is already sorted by definition. 
  The check for that is the line

   if len(alist)>1:

near the beginning of the function.  That's analogous to my if n==0 
line, although to match it most directly, I could have reversed the 
if/else and written the test as if n!=0

Chris showed you how to change your output so you could see the nesting 
levels.  I have done that sort of thing in the past, and found it very 
useful.  But first you have to understand nested functions, and simple 
recursion.


-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#46478

On Thursday, May 30, 2013 6:09:20 PM UTC+5:30, bhk...@gmail.com wrote:
> Thanks Chris, Wolfgang and Joshua for your replies.
> 
> 
> 
> ---
> 
> In step 2b, all the steps from 1 through 3 are executed again (twice). 
> 
> Soon, those calls will just output "Splitting" followed by "Merging"; 
> 
> and then we go back to 2c. That's why it *seems* that the code goes 
> 
> from 3 to 2c. You'll notice that the call depth decreases when this 
> 
> happens
> 
> 
> 
> Chris, Can you please let me know what makes the control of the program code go to  2c after the output "Merging". 
> 
> Also, please look into the following output for the same program with more print statements, 
> ---------------------------------------------- 
>  before calling main mergesort 
> 
>  Splitting [54, 26, 93, 17, 77, 31, 44, 55, 20]
> 
> left half before split  [54, 26, 93, 17]
> 
> right half before split [77, 31, 44, 55, 20]
> 
>   Splitting [54, 26, 93, 17]
> 
> left half before split  [54, 26]
> 
> right half before split [93, 17]
> 
>     Splitting [54, 26]
> 
> left half before split  [54]
> 
> right half before split [26]
> 
>       Splitting [54]
> 
>       Merging [54]
> 
>       Splitting [26]
> 
>       Merging [26]
> 
> 
> 
> HERE AFTER SPLIT
> 
> 
> 
> left half after split [54]
> 
> right half after split [26]
> 
>     Merging [26, 54]
> 
>     Splitting [93, 17]
> 
> left half before split  [93]
> 
> right half before split [17]
> 
>       Splitting [93]
> 
>       Merging [93]
> 
>       Splitting [17]
> 
>       Merging [17]
> 
> 
> 
> HERE AFTER SPLIT
> 
> 
> 
> left half after split [93]
> 
> right half after split [17]
> 
>     Merging [17, 93]
> 
> 
> 
> HERE AFTER SPLIT
> 
> 
> 
> left half after split [26, 54]
> 
> right half after split [17, 93]
> 
>   Merging [17, 26, 54, 93]
> 
>   Splitting [77, 31, 44, 55, 20]
> 
> left half before split  [77, 31]
> 
> right half before split [44, 55, 20]
> 
>     Splitting [77, 31]
> 
> left half before split  [77]
> 
> right half before split [31]
> 
>       Splitting [77]
> 
>       Merging [77]
> 
>       Splitting [31]
> 
>       Merging [31]
> 
> 
> 
> HERE AFTER SPLIT
> 
> 
> 
> left half after split [77]
> 
> right half after split [31]
> 
>     Merging [31, 77]
> 
>     Splitting [44, 55, 20]
> 
> left half before split  [44]
> 
> right half before split [55, 20]
> 
>       Splitting [44]
> 
>       Merging [44]
> 
>       Splitting [55, 20]
> 
> left half before split  [55]
> 
> right half before split [20]
> 
>         Splitting [55]
> 
>         Merging [55]
> 
>         Splitting [20]
> 
>         Merging [20]
> 
> 
> 
> HERE AFTER SPLIT
> 
> 
> 
> left half after split [55]
> 
> right half after split [20]
> 
>       Merging [20, 55]
> 
> 
> 
> HERE AFTER SPLIT
> 
> 
> 
> left half after split [44]
> 
> right half after split [20, 55]
> 
>     Merging [20, 44, 55]
> 
> 
> 
> HERE AFTER SPLIT
> 
> 
> 
> left half after split [31, 77]
> 
> right half after split [20, 44, 55]
> 
>   Merging [20, 31, 44, 55, 77]
> 
> 
> 
> HERE AFTER SPLIT
> 
> 
> 
> left half after split [17, 26, 54, 93]
> 
> right half after split [20, 31, 44, 55, 77]
> 
>  Merging [17, 20, 26, 31, 44, 54, 55, 77, 93]
> 
> 
> 
>  after calling main mergesort
> 
> 
> 
> [17, 20, 26, 31, 44, 54, 55, 77, 93]
> 
> -------------------------------------------------------
>  
> In the above output, the control goes to "HERE AFTER SPLIT" after the "Merging" statement which is of-course the last statement in the function.On what condition this is happening.
> 
> Ideally as per my understanding, after the last statement of a function the control should come out of the function. 
> 
> Please correct me if I am wrong here.
> 
> There is something with respect-to functions in python that I am not able to understand.

[toc] | [prev] | [next] | [standalone]

#46481

On Thu, May 30, 2013 at 10:39 PM,  <bhk755@gmail.com> wrote:
> Chris, Can you please let me know what makes the control of the program code go to  2c after the output "Merging".


It goes like this:

1. [eight element list]
2a. [eight element list]
2b.   1. [four element list]
2b.   2a. [four element list]
2b.   2b.    1. [two element list]
2b.   2b.    2a. [two element list]
2b.   2b.    2b. [two element list]
2b.   2b.    2b.    1. [one element list]
2b.   2b.    2b.    2. [one element list]
2b.   2b.    2b.    3. [one element list]
2b.   2b.    2c. [two element list]
2b.   2b.    3. [two element list]
... etc etc etc ...

Notice how control actually flows from 1, to 2a, to 2b, to 2c, but in
between, it goes back to 1? That's recursion. There are four separate
function calls here, which you can see going down the page. Each time
it gets to step 2b, a whole new "thread" starts, and the previous one
doesn't do anything till the inner one reaches step 3 and finishes.

That's why the indented output can help; eyeball them going down and
you'll see that they don't do anything until the inner one finishes.

ChrisA

[toc] | [prev] | [next] | [standalone]

#46486

Thanks Chris, Wolfgang and Joshua for your replies. 
------------------------

In step 2b, all the steps from 1 through 3 are executed again (twice). 

Soon, those calls will just output "Splitting" followed by "Merging"; 

and then we go back to 2c. That's why it *seems* that the code goes 

from 3 to 2c. You'll notice that the call depth decreases when this 

happens 

Chris, Can you please let me know what makes the control of the program code go to  2c after the output "Merging". 

Also, please look into the following output for the same program with more print statements, 
---------------------------------------------- 
 before calling main mergesort 
 Splitting [54, 26, 93, 17, 77, 31, 44, 55, 20] 
left half before split  [54, 26, 93, 17] 
right half before split [77, 31, 44, 55, 20] 
  Splitting [54, 26, 93, 17] 
left half before split  [54, 26] 
right half before split [93, 17] 
    Splitting [54, 26] 
left half before split  [54] 
right half before split [26] 
      Splitting [54] 
      Merging [54] 
      Splitting [26] 
      Merging [26] 
HERE AFTER SPLIT 
left half after split [54] 
right half after split [26] 
    Merging [26, 54] 
    Splitting [93, 17] 
left half before split  [93] 
right half before split [17] 
      Splitting [93] 
      Merging [93] 
      Splitting [17] 
      Merging [17] 
HERE AFTER SPLIT 
left half after split [93] 
right half after split [17] 
    Merging [17, 93] 
HERE AFTER SPLIT 
left half after split [26, 54] 
right half after split [17, 93] 
  Merging [17, 26, 54, 93] 
  Splitting [77, 31, 44, 55, 20] 
left half before split  [77, 31] 
right half before split [44, 55, 20] 
    Splitting [77, 31] 
left half before split  [77] 
right half before split [31] 
      Splitting [77] 
      Merging [77] 
      Splitting [31] 
      Merging [31] 
HERE AFTER SPLIT 
left half after split [77] 
right half after split [31] 
    Merging [31, 77] 
    Splitting [44, 55, 20] 
ft half before split  [44] 
ght half before split [55, 20] 
     Splitting [44] 
      Merging [44] 
      Splitting [55, 20] 
eft half before split  [55] 
ight half before split [20] 
       Splitting [55] 
       Merging [55] 
       Splitting [20] 
       Merging [20] 
HERE AFTER SPLIT 
left half after split [55] 
right half after split [20] 
      Merging [20, 55] 
HERE AFTER SPLIT 
left half after split [44] 
right half after split [20, 55] 
    Merging [20, 44, 55] 
HERE AFTER SPLIT 
left half after split [31, 77] 
right half after split [20, 44, 55] 
Merging [20, 31, 44, 55, 77] 
HERE AFTER SPLIT 
left half after split [17, 26, 54, 93] 
right half after split [20, 31, 44, 55, 77] 
 Merging [17, 20, 26, 31, 44, 54, 55, 77, 93] 
 after calling main mergesort 
[17, 20, 26, 31, 44, 54, 55, 77, 93] 
------------------------------------------------------- 
   
In the above output, the control goes to "HERE AFTER SPLIT" after the "Merging" statement which is of-course the last statement in the function.On what condition this is happening. 
Ideally as per my understanding, after the last statement of a function the control should come out of the function. 
Please correct me if I am wrong here. 
There is something with respect-to functions in python that I am not able to understand. 

[toc] | [prev] | [next] | [standalone]

#46572

Got It!!!,  Finally.  Thanks Dave

So, the control goes back to the place after the recursive function is called once the no. of element is equal to one and starts merging after which it will again start to split the remaining items.

Thank you Chris for your multiple explanations. It was also very useful.

One final question, Is there a way to edit the message once it has been posted?

[toc] | [prev] | [next] | [standalone]

#46573

Got It!!!,  Finally.  Thanks Dave 

So, the control goes back to the place after the recursive function is called once the no. of element is equal to one and starts merging after which it will again start to split the remaining items. 

Thank you Chris for your multiple explanations.

One final question, Is there a way to edit the message once it has been posted? 

[toc] | [prev] | [next] | [standalone]

#46575

On 30May2013 21:54, bhk755@gmail.com <bhk755@gmail.com> wrote:
| One final question, Is there a way to edit the message once it has been posted? 

Essentially, no. If there's some error in a post, reply to it
yourself with a correction. Transparency is a good thing. Revisionist
history pretty much is not.
-- 
Cameron Simpson <cs@zip.com.au>

Well, it's one louder, isn't it?  It's not ten.  You see, most blokes are
gonna be playing at ten, you're on ten here, all the way up, all the way up,
all the way up, you're on ten on your guitar, where can you go from there?
Where?  Nowhere, exactly.  What we do is, if we need that extra push over the
cliff, you know what we do?  Eleven.  Exactly.  One louder.
        - Nigel Tufnel, _This Is Spinal Tap_

[toc] | [prev] | [next] | [standalone]

#46578

On Fri, May 31, 2013 at 3:43 PM, Cameron Simpson <cs@zip.com.au> wrote:
> On 30May2013 21:54, bhk755@gmail.com <bhk755@gmail.com> wrote:
> | One final question, Is there a way to edit the message once it has been posted?
>
> Essentially, no. If there's some error in a post, reply to it
> yourself with a correction. Transparency is a good thing. Revisionist
> history pretty much is not.

Once your email or newsgroup post is sent, assume that it's also been
received; at very least, you won't be far wrong. You'll sometimes see
a response within minutes from someone who saw your post within
seconds.

ChrisA

[toc] | [prev] | [next] | [standalone]

#46669

On May 30, 2:48 pm, bhk...@gmail.com wrote:
> Code :
> -----
> def mergeSort(alist):
>     print("Splitting ",alist)
>     if len(alist)>1:
>         mid = len(alist)//2
>         lefthalf = alist[:mid]
>         righthalf = alist[mid:]
>
>         mergeSort(lefthalf)
>         mergeSort(righthalf)
>
>         i=0
>         j=0
>         k=0
>         while i<len(lefthalf) and j<len(righthalf):
>             if lefthalf[i]<righthalf[j]:
>                 alist[k]=lefthalf[i]
>                 i=i+1
>             else:
>                 alist[k]=righthalf[j]
>                 j=j+1
>             k=k+1
>
>         while i<len(lefthalf):
>             alist[k]=lefthalf[i]
>             i=i+1
>             k=k+1
>
>         while j<len(righthalf):
>             alist[k]=righthalf[j]
>             j=j+1
>             k=k+1
>     print("Merging ",alist)
>
> alist = [54,26,93,17,77,31,44,55,20]
> mergeSort(alist)
> print(alist)
>
> Output:
> -------
> ('Splitting ', [54, 26, 93, 17, 77, 31, 44, 55, 20])
> ('Splitting ', [54, 26, 93, 17])
> ('Splitting ', [54, 26])
> ('Splitting ', [54])
> ('Merging ', [54])
> ('Splitting ', [26])
> ('Merging ', [26])
> ('Merging ', [26, 54])
> ('Splitting ', [93, 17])
> ('Splitting ', [93])
> ('Merging ', [93])
> ('Splitting ', [17])
> ('Merging ', [17])
> ('Merging ', [17, 93])
> ('Merging ', [17, 26, 54, 93])
> ('Splitting ', [77, 31, 44, 55, 20])
> ('Splitting ', [77, 31])
> ('Splitting ', [77])
> ('Merging ', [77])
> ('Splitting ', [31])
> ('Merging ', [31])
> ('Merging ', [31, 77])
> ('Splitting ', [44, 55, 20])
> ('Splitting ', [44])
> ('Merging ', [44])
> ('Splitting ', [55, 20])
> ('Splitting ', [55])
> ('Merging ', [55])
> ('Splitting ', [20])
> ('Merging ', [20])
> ('Merging ', [20, 55])
> ('Merging ', [20, 44, 55])
> ('Merging ', [20, 31, 44, 55, 77])
> ('Merging ', [17, 20, 26, 31, 44, 54, 55, 77, 93])
> [17, 20, 26, 31, 44, 54, 55, 77, 93]
>
> Question:
> ---------
> Function mergeSort is called only once, but it is getting recursively executed after the printing the last statement "print("Merging ",alist)". But don't recursion taking place except at these places "mergeSort(lefthalf), mergeSort(righthalf)"
>
> Sometimes the function execution directly starts from i=0,j=0,k=0 . Not sure how.
>
> Can anyone please help me out here?

Not in direct answer to your question... Still see if this helps you
to understand mergesorting better.

I generally find that mixing recursion along with imperative
programming makes recursion look difficult.
Imperative programming goes scot-free and recursion gets a bad name!!

So here is a pure recursive/functional solution.  Tell me if you
understand it better (or worse!!)
Its written to demonstrate the IDEA of mergesort. Its actual
efficiency is sub-par for various reasons.

-------------------------------------
# merging two lists, both assumed sorted
def merge(a,b):
    if a == []: return b
    elif b== []: return a
    elif a[0] < b[0]:
        return [a[0]] + merge(a[1:],b)
    else:
        return [b[0]] + merge(a,b[1:])

# The same as merge above written in pure functional style
def merge1(a,b):
    return (b if a == [] else
            a if b == [] else
            [a[0]] + merge(a[1:],b) if a[0] < b[0] else
            [b[0]] + merge(a,b[1:])
           )

def mergeSort(alist):
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]
        return merge1(mergeSort(lefthalf),mergeSort(righthalf) )
    else:
        return alist

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web