[Tutor] learning recursion

[rakesh sharma]

Hi
I guess I need to revisit my maths lessons.Thank you for correcting me. 
thanks,rakesh

> From: dyoo at hashcollision.org
> Date: Sat, 8 Feb 2014 00:20:19 -0800
> Subject: Re: [Tutor] learning recursion
> To: rakeshsharma14 at hotmail.com
> CC: davea at davea.name; tutor at python.org
> 
> On Fri, Feb 7, 2014 at 9:05 PM, rakesh sharma
> <rakeshsharma14 at hotmail.com> wrote:
> > Hi
> >
> > Shouldn't your code be like this
> >
> > def fib(n):
> > if n==0:
> > return 0
> > else:
> > return n + fib(n-1)
> 
> 
> Hi Rakesh,
> 
> Unfortunately, no, because this computes a slightly different
> function: the triangular numbers!  :P
> 
> 
> That is, your function above is an implementation for the sum:
> 
>     0 + 1 + 2 + ... + n
> 
> It's also known as a "Gauss sum".
> 
> 
> ##################################################################
> 
> [Tangent ahead.  Skip if you're not interested.]
> 
> As a very tangent note, it's good for us programmers to know about
> this function, because it shows up in some common places.  For
> example, it occurs when we try to figure out approximately how long it
> takes to concatenate a bunch of strings in a naive way.
> 
> Imagine the following artificial scenario:
> 
> #############################
> long_string = ""
> for n in range(1000):
>     long_string = long_string + "X"
> #############################
> 
> where we're building up a large string with repeated concatenations.
> 
> Does this look bad to you?  It should!  The string concatenation
> operation takes time that's proportional to the size of the string
> we're building up.  If we do the above, with _repeated_ string
> concatenation, going through the whole loop will cost, altogether,
> something on the order of:
> 
>     0 + 1 + 2 + ... + 1000
> 
> elementary operations, representing the first, second, ... and
> thousandth time through that loop.
> 
> And if you know your Gauss sum, this sum can be quickly computed
> without having to do each individual addition:
> 
>     0 + 1 + 2 + ... + 1000
>         = (1000 * 1001) / 2
>         = 500500
> 
> which is a fairly big number.
> 
> In general:
> 
>     0 + 1 + 2 + ... + n
>         = n * (n+1) / 2
> 
> In practice, this means for us programmers that if we're going to
> build up a large string in parts, doing repeated string concatenation
> is not the right approach as it means we're doing things in quadratic
> time.  It's better to build up a list of strings, and then do the
> concatenation all at once, avoiding the repeating rebuilding of a
> larger and larger string:
> 
> #############################
> long_string_chunks = []
> for n in range(1000):
>     long_string_chunks.append("X")
> long_string = "".join(long_string_chunks)
> #############################
> 
> where the "".join(...) part, having been implemented well, and knowing
> all the long_string_chunk elements, can do the string concatenation in
> one single, efficient pass.
 		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20140208/7fcfb648/attachment.html>