On Fri, Feb 7, 2014 at 9:05 PM, rakesh sharma <rakeshsharm...@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. _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor