Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.mixmin.net!rt.uk.eu.org!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Date: Thu, 30 May 2013 09:29:52 -0400
From: Dave Angel <davea@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130510 Thunderbird/17.0.6
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: Can anyone please help me in understanding the following python code
References: <921173f3-21e7-46b4-a7b1-86660a3ebc72@googlegroups.com> <384a9b8f-40e0-4c8c-b15f-0c96512f67f1@googlegroups.com> <ccb5c332-4b5e-44e3-ab9b-1d815c73548b@googlegroups.com>
In-Reply-To: <ccb5c332-4b5e-44e3-ab9b-1d815c73548b@googlegroups.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.2420.1369920608.3114.python-list@python.org>
Lines: 104
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python: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