[Tutor] learning recursion

[Danny Yoo]

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.