Some Programs involving Recursion

We can find a^b using recursion.The code is..

def power(a, b):
if (b == 0):
return 1
else:
a=a*power(a, b-1)
return a

print power(3, 9)


We can optimise the above program and reduce the time complexity.
Here is the code for that..

def power(a, b):
if(b == 0):
return 1
else:
if(b%2 == 0):
v = power(a, b/2)
return v**2
else:
v = power(a, (b-1)/2)
return a*v**2

print power(3, 5)


Next we can move on to finding the nth element of Fibonacci series.
For that we have a recursive code..

def fib(n):
if n<2 :
return n
else:
return fib(n-1)+fib(n-2)

print fib(6)


We can optimise the above code using the technique of memorisation.
Then the code will be..

def fib(n):
if not n in memory:
memory[n] = fib(n-1) + fib(n-2)
return memory[n]

memory={0:0,1:1}
print fib (250)

Python Generators

When we write a program it mat contain a series of named blocks. Each of those performs a single logical action. Named blocks are usually performed one after another as a sequence of statements from within another block.

In this example, the pow2 function is performed completely before the for loop is run.

The list called "powers" is constructed completely and stored in memory while the for loop is run. That's not a problem in this case with a list of ten values, but it could be a problem if the list was to contain a billion values.

def pow2(upto):
powers = []
sat = 1
spwr = 1
while spwr <= upto:
powers.append(sat)
sat *= 2
spwr += 1
return powers

def main():
for w in pow2(10):
print w
main()


Python provides an alternative way.i.e. Generator Functions. A generator function is one that does NOT run to completion when it's first called - instead, it only runs until it has a value available to return.

A generator function is any function which uses the yield statement.

When the for loop asks for the next element the generator starts or continues function execution at the place it left off. It runs until it reaches a yield statement. The function call is suspended at the yield statement. The generator stores the function call state and returns the given element.

Here's the program provided above, modified to use a generator.

def pow2(upto):
sat=1
spwr=1
while spwr<=upto:
yield sat
sat*=2
spwr+=1

def main():
for w in pow2(10):
print w
main()

Operation is exactly the same as the example above ... but there is NOT an intermediate list produced.Generators provide a very neat way of providing data as required on applications that potentially use huge intermediate lists.

List comprehensions

Python supports a concept called "list comprehensions". It can be used to construct lists in a very easy way.

In mathematics we can describe lists this way:

S = {x² : x in {0 ... 9}}
V = (1, 2, 4, 8, ..., 2¹²)
M = {x | x in S and x even}

In Python we can do this as::

>>> S = [x**2 for x in range(10)]
>>> V = [2**i for i in range(13)]
>>> M = [x for x in S if x % 2 == 0]

Let's see the result:

>>> print S
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
>>>print V
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]
>>>print M
[0, 4, 16, 36, 64]

More examples:

>>> [(x, x**2) for x in vec]
[(2, 4), (4, 16), (6, 36)]
>>> vec1 = [2, 4, 6]
>>> vec2 = [4, 3, -9]
>>> [x*y for x in vec1 for y in vec2]
[8, 6, -18, 16, 12, -36, 24, 18, -54]
>>> [x+y for x in vec1 for y in vec2]
[6, 5, -7, 8, 7, -5, 10, 9, -3]
>>> [vec1[i]*vec2[i] for i in range(len(vec1))]
[8, 12, -54] 

any type of elements, including strings, nested lists and functions. We can even mix different types within a list.

list comprehensions work for any type of elements

>>> words='You can nest list comprehensions inside of each other'.split()
>>> words
['You', 'can', 'nest', 'list', 'comprehensions', 'inside', 'of', 'each', 'other']
>>> new=[[w.upper(), w.lower(), len(w)] for w in words]
>>> for i in new:
... print i
...
['YOU', 'you', 3]
['CAN', 'can', 3]
['NEST', 'nest', 4]
['LIST', 'list', 4]
['COMPREHENSIONS', 'comprehensions', 14]
['INSIDE', 'inside', 6]
['OF', 'of', 2]
['EACH', 'each', 4]
['OTHER', 'other', 5]
>>>





Strings

Python has a built-in String class named "str".String literals can be enclosed in single or double quotes.
Consider for example:
>>> print "hai friend \n are you fine"
hai friend
are you fine

Suppose we want to get \n, \t etc in our sentence we have to add r before the quotes.
>>> print r"hai friend \n are you fine"
hai friend \n are you fine

There are a number of operations on strings.
Concatenation is done with the + operator.
>>> "hi"+" friend"
'hi friend'

Suppose we want to concatenate a string with a number, we can convert number to a string with the str casting function, otherwise,
>>> pi=3.14
>>> text='The value of pi is '+pi
Traceback (most recent call last):
File "", line 1, in
TypeError: cannot concatenate 'str' and 'float' objects

So we can concatenate these by,
>>> pi=3.14
>>> text='The value of pi is '+str(pi)
>>> text
'The value of pi is 3.14'

The * operator between strings and numbers creates a new string that is a number of repetitions of the input string.

>>> print 3*"cool !"
cool !cool !cool !

Comparing Strings:Strings can be compared with the standard operators :
==, !=, <, >, <=, and >=. 

String methods

s.lower,s.upper -returns the lowercase or uppercase version of the string.
s.startwith('other'),s.endwith('other') - tests if the string start with or end with the given other string
s.find('other') - searches for the given other string and returns the first index where it begins.Otherwise return -1.
s.replace('old','new') - returns a string where all occurences of 'old' have been replaced by new.

Extracting substrings: Strings in Python can be subscripted just like an array: s[4] = 'a'. Two indices separated by a colon, will return a substring containing characters index1 through index2-1. Indices can also be negative, in which case they count from the right, i.e. -1 is the last character. Thus substrings can be extracted like,
>>> s="beautiful"
>>> s[1:4]
'eau'
>>> s[:5]
'beaut'
>>> s[3:]
'utiful'
>>> s[-7:-2]
'autif'

String % : Python has % operator which takes a printf-type format string on the left (%d,%s),and matching values separated by commas.
>>> text="%d little girls are dancing with their %s"%(3,"mother")
>>> text
'3 little girls are dancing with their mother'

Variables

Variables are reserved memory locations to store values. So When we create a variable we reserve space in memory according to the data type of the variable. The interpreter allocates memory .

Assigning values to variables

Python variables do not have to be explicitly declared. The declaration happens automatically when we assign a value to a variable. The equal sign (=) is used to assign values to variables.

The operand to the left of the = operator is the name of the variable, and the operand to the right of the = operator is the value stored in the variable.

For example:

>>> c=100
>>> m=123.34
>>> name="john"

Python doesn't have the same types as C/C++, which appears to be your question.

For example:

>>> i = 123
>>> type(i)
<type 'int'>
>>> type(i) is int
True
>>> i = 123456789L
>>> type(i)
<type 'long'>
>>> type(i) is long
True
>>> i = 123.456
>>> type(i)
<type 'float'>
>>> type(i) is float
True

Multiple Assignment : You can also assign a single value to several variables simultaneously.

For example:

>>> a=d=s=2
>>> a
2
>>> d
2
>>> s
2

Here, an integer object is created with the value 1, and all three variables are assigned to the same memory location. You can also assign multiple objects to multiple variables.

For example:

>>> a,b,c=2,4,"dfg"
>>> a
2
>>> b
4
>>> c
'dfg'
>>>

Python numbers : Number data types store numeric values. They are immutable data types, which means that changing the value of a number data type results in a newly allocated object.

Number objects are created when you assign a value to them.

For example:

>>> a=1
>>> d=3
>>> f=7

You can delete a single object or multiple objects by using the del statement.

For example:

>>> del a
>>> del d,f

Introduction to python

Python is an easy to learn and powerful programming language.In python code is automatically compiled to byte code and executed.So python can be used as a scripting language.

Features of python

• Simple and Easy to Learn

• Free and Open Source

• High-level Language

• Built-in high level data types: strings, lists, dictionaries.

• The usual control structures: if, if-else, if-elif-else, while.

• Multiple levels of organizational structure: functions, classes, modules, and packages.

Python programs are executed by interpreters. There are two modes to use the interpreter.

• Interactive mode
  

On a Linux platform you should be able to do this by typing python at a command prompt. On windows you should double click on the Python icon.This will launch the interactive interpreter.

Python 2.6.6 (r266:84292, Sep 15 2010, 15:52:39)
[GCC 4.4.5] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 34+45
79
>>> a="haiii"
>>> a
'haiii'
>>> len(a)
5
>>>

• Script mode In script mode code is stored in a file.Interpreter is used to execute the contents of the file.Python scripts saved with extension .py.

Creating and running programs

Python programs are just text files that contain instructions for the Python interpreter. You can create them with any text editor .In Linux we can run the program by typing something like ./program.py.

Comment : Any line which starts with a hash (#) is a comment. It will be skipped by the interpreter. There is no multi line comment in Python, you should start every line with a hash instead.

Indentation: In python white space indentation effect the meaning.A logical block will have the same indentation.If one of the line of a logical block has a different indentation it will result in syntax error.

Code is checked at runtime: Python does very little checking at compile time.Python only checks a line when it runs that line.