Hello, World!

Python is a very simple language, and has a very straightforward syntax. It encourages programmers to program without boilerplate (prepared) code. The simplest directive in Python is the "print" directive - it simply prints out a line (and also includes a newline, unlike in C).

Python is an easy to learn, powerful programming language. It has efficient high-level data structures and a simple but effective approach to object-oriented programming. Python’s elegant syntax and dynamic typing, together with its interpreted nature, make it an ideal language for scripting and rapid application development in many areas on most platforms.

Python is Interpreted - Python is processed at runtime by the interpreter. You do not need to compile your program before executing it. This is similar to PERL and PHP.

Python is widely used in Artificial Intelligence, Natural Language Generation, Neural Networks and other advanced fields of Computer Science. Python had deep focus on code readability & this class will teach you python from basics. So if you want to start learning AI or deep learning. Learning python is a great start !

To print a string, just write:

print ("Hello World!")

Readability

Python is all about ease. It is a very readable language. Python has Python uses indentation for blocks, instead of curly braces. Both tabs and spaces are supported, but the standard indentation requires standard Python code to use four spaces. 

For example:

a=0
def printfnc():
 print (a)
printfnc() 

Types

It's a lot easier in Python. There is no declaration of variables required in Python. It's not even possible. If there is need of a variable, you think of a name and start using it as a variable.

Another remarkable aspect of Python: Not only the value of a variable may change during program execution but the type as well. You can assign an integer value to a variable, use it as an integer for a while and then assign a string to the same variable.
In the following line of code, we assign the value 42 to a variable:

i = 42

The equal "=" sign in the assignment shouldn't be seen as "is equal to". It should be "read" or interpreted as "is set to", meaning in our example "the variable i is set to 42". Now we will increase the value of this variable by 1:

>> i = i + 1
>>> print(i)
43
>>> 

As we have said above, the type of a variable can change during the execution of a script. Or to be precise: A new object, which can be of any type, will be assigned to it. We illustrate this in our following example:

i = 42   # data type is implicitly set to integer
i = 42 + 0.11  # data type is changed to float
i = "forty"  # and now it will be a string 
 

Python automatically takes care of the physical representation for the different data types, i.e. an integer values will be stored in a different memory location than a float or a string.

Object References

We want to take a closer look on variables now. Python variables are references to objects, but the actual data is contained in the objects: As variables are pointing to objects and objects can be of arbitrary data type, variables cannot have types associated with them. This is a huge difference to C, C++ or Java, where a variable is associated with a fixed data type. This association can't be changed as long as the program is running. Therefore it is possible to write code like the following in Python:

>>> x = 42
>>> print(x)
42
>>> x = "Now x references a string"
>>> print(x)
Now x references a string

We want to demonstrate something else now. Let's look at the following code:

>>> x = 42
>>> y = x

We created an integer object 42 and assigned it to the variable x. After this we assigned x to the variable y. This means that both variables reference the same object. The following picture illustrates this: What will happen, when we execute

y = 78

after the previous code? Python will create a new integer object with the content 78 and then the variable y will reference this newly created object, as we can see in the following picture: Most probably, we will see further changes to the variables in the flow of our program. There might be for example a string assignment to the variable x. The previously integer object "42" will be orphaned after this assignment. It will be removed by Python, because no other variable is referencing it.

id Function

You may ask yourself, how can we see or prove that x and y really reference the same object after the assignment y = x of our previous example?

The identity function id() can be used for this purpose. Every instance (object or variable) has an identity, i.e. an integer which is unique within the script or program, i.e. other objects have different identities.
So, let's have a look at our previous example and how the identities will change:

>>> x = 42
>>> id(x)
10107136
>>> y = x
>>> id(x), id(y)
(10107136, 10107136)
>>> y = 78
>>> id(x), id(y)
(10107136, 10108288)
>>> 

Valid Variable Names

The naming of variables follows the more general concept of an identifier. A Python identifier is a name used to identify a variable, function, class, module or other object.
A variable name and an identifier can consist of the uppercase letters "A" through "Z", the lowercase letters "a" through "z" , the underscore _ and, except for the first character, the digits 0 through 9. Python 3.x is based on Unicode. This means that variable names and identifier names can additionally contain Unicode characters as well. But in Python 2, identifiers can only be ASCII letters, numbers and underscores.
Identifiers are unlimited in length. Case is significant. The fact that identifier names are case-sensitive can cause problems to some Windows users, where file names are case-insensitive for example.

Standard Data Types

• Numbers
• String
• List
• Tuple
• Dictionary

Numbers

Python supports four types of numbers - int,long,float and complex
For example
3(int),4.0(float),51924361L(long),3.14j(complex)A complex number consists of an ordered pair of real floating-point numbers denoted by x + yj, where x and y are the real numbers and j is the imaginary unit.

To define an integer, use the following syntax:

    
myint = 7

To define a floating point number, you may use one of the following notations:

myfloat = 7.0
myfloat = float(7)
    

Strings

Strings are defined either with a single quote or a double quotes.

    
mystring = 'hello'
mystring = "hello"

There are additional variations on defining strings that make it easier to include things such as carriage returns, backslashes and Unicode characters. These are beyond the scope of this tutorial, but are covered in the Python documentation.

Simple operators can be executed on numbers and strings:

    
one = 1
two = 2
three = one + two
hello = "hello"
world = "world"
helloworld = hello + " " + world

Assignments can be done on more than one variable "simultaneously" on the same line like this

a, b = 3, 4

Lists

Lists are the most versatile of Python's compound data types. A list contains items separated by commas and enclosed within square brackets ([]). To some extent, lists are similar to arrays in C. One difference between them is that all the items belonging to a list can be of different data type.
The values stored in a list can be accessed using the slice operator ([ ] and [:]) with indexes starting at 0 in the beginning of the list and working their way to end -1. The plus (+) sign is the list concatenation operator, and the asterisk (*) is the repetition operator. For example −

list = [ 'abcd', 786 , 2.23, 'john', 70.2 ]
tinylist = [123, 'john']

print list          # Prints complete list
print list[0]       # Prints first element of the list
print list[1:3]     # Prints elements starting from 2nd till 3rd 
print list[2:]      # Prints elements starting from 3rd element
print tinylist * 2  # Prints list two times
print list + tinylist # Prints concatenated lists

Tuples

A tuple is another sequence data type that is similar to the list. A tuple consists of a number of values separated by commas. Unlike lists, however, tuples are enclosed within parentheses.
The main differences between lists and tuples are: Lists are enclosed in brackets ( [ ] ) and their elements and size can be changed, while tuples are enclosed in parentheses ( ( ) ) and cannot be updated. Tuples can be thought of as read-onlylists. For example

tuple = ( 'abcd', 786 , 2.23, 'john'  )

print tuple           # Prints complete list
print tuple[0]        # Prints first element of the list
print tuple[1:3]      # Prints elements starting from 2nd till 3rd 
print tuple[2:]       # Prints elements starting from 3rd element

Lists

Lists are very similar to arrays. They can contain any type of variable, and they can contain as many variables as you wish. Lists can also be iterated over in a very simple manner.

This section will give you a more deeper insight on lists

Here is an example of how to build a list.

Two common operations are indexing and assigning to an index position. Both of these operations take the same amount of time no matter how large the list becomes. When an operation like this is independent of the size of the list they are O(1)O(1).

Another very common programming task is to grow a list. There are two ways to create a longer list. You can use the append method or the concatenation operator. The append method is O(1)O(1). However, the concatenation operator is O(k)O(k) where kk is the size of the list that is being concatenated. This is important for you to know because it can help you make your own programs more efficient by choosing the right tool for the job.

Let’s look at four different ways we might generate a list of n numbers starting with 0. First we’ll try a for loop and create the list by concatenation, then we’ll use append rather than concatenation. Next, we’ll try creating the list using list comprehension and finally, and perhaps the most obvious way, using the range function wrapped by a call to the list constructor.

    
def test1():
    l = []
    for i in range(1000):
        l = l + [i]

def test2():
    l = []
    for i in range(1000):
        l.append(i)

def test3():
    l = [i for i in range(1000)]

def test4():
    l = list(range(1000))

list=[1,'abc',2] 
     
     

Basic List Operations

Lists respond to the + and * operators much like strings; they mean concatenation and repetition here too, except that the result is a new list, not a string.

In fact, lists respond to all of the general sequence operations we used on strings in the prior chapter.

Python Expression	Results	Description
len([1, 2, 3])	3	Length
[1, 2, 3] + [4, 5, 6]	[1, 2, 3, 4, 5, 6]	Concatenation
['Hi!'] * 4	['Hi!', 'Hi!', 'Hi!', 'Hi!']	Repetition
3 in [1, 2, 3]	True	Membership
for x in [1, 2, 3]: print x,	1 2 3	Iteration

Updating Lists

You can update single or multiple elements of lists by giving the slice on the left-hand side of the assignment operator, and you can add to elements in a list with the append() method. For example -

    
list = ['physics', 'chemistry', 1997, 2000];
print "Value available at index 2 : "
print list[2]
list[2] = 2001;
print "New value available at index 2 : "
print list[2]
     
     

Deleting List Elements

To remove a list element, you can use either the del statement if you know exactly which element(s) you are deleting or the remove() method if you do not know. For example -

     

list1 = ['physics', 'chemistry', 1997, 2000];
print list1
del list1[2];
print "After deleting value at index 2 : "
print list1

Indexing, Slicing, and Matrixes

Because lists are sequences, indexing and slicing work the same way for lists as they do for strings.
Assuming following input −

L = ['spam', 'Spam', 'SPAM!']

Python Expression	Results	Description
L[2]	'SPAM!'	Offsets start at zero
L[-2]	'Spam'	Negative: count from the right
L[1:]	['Spam', 'SPAM!']	Slicing fetches sections

Built-in List Functions & Methods

Python includes the following list functions −

Sr.No.	Function with Description
1	cmp(list1, list2)Compares elements of both lists.
2	len(list)Gives the total length of the list.
3	max(list)Returns item from the list with max value.
4	min(list)Returns item from the list with min value.
5	list(seq)Converts a tuple into list.

Basic Operators

This section explains how to use basic operators in Python.

Arithmetic Operators

Just as any other programming languages, the addition, subtraction, multiplication, and division operators can be used with numbers.
Try to predict what the answer will be. Does python follow order of operations?

   
    number = 1 + 2 * 3 / 4.0
print number 

Another operator available is the modulo (%) operator, which returns the integer remainder of the division. dividend % divisor = remainder.

remainder = 11 % 3
print remainder

Using two multiplication symbols makes a power relationship.

     
squared = 7 ** 2
cubed = 2 ** 3
print squared
print cubed

Using Operators with Strings

Python supports concatenating strings using the addition operator:

helloworld = "hello" + " " + "world"
print helloworld
lotsofhellos = "hello" * 10
print lotsofhellos

Operator	Description	Example
+, -	Addition, Subtraction	10 -3
*, %	Multiplication, Modulo	27 % 7 Result: 6
/	Division This operation results in different results for Python 2.x (like floor division) and Python 3.x	Python3: >>> 10 / 3 3.3333333333333335 and in Python 2.x: >>> 10 / 3 3
//	Truncation Division (also known as floordivision or floor division) The result of this division is the integral part of the result, i.e. the fractional part is truncated, if there is any. It works both for integers and floating-point numbers, but there is a difference in the type of the results: If both the divident and the divisor are integers, the result will be also an integer. If either the divident or the divisor is a float, the result will be the truncated result as a float.	>>> 10 // 3 3 If at least one of the operands is a float value, we get a truncated float value as the result. >>> 10.0 // 3 3.0 >>> A note about efficiency: The results of int(10 / 3) and 10 // 3 are equal. But the "//" division is more than two times as fast! You can see this here: In [9]: %%timeit for x in range(1, 100): y = int(100 / x) ...: 100000 loops, best of 3: 11.1 μs per loop In [10]: %%timeit for x in range(1, 100): y = 100 // x ....: 100000 loops, best of 3: 4.48 μs per loop
+x, -x	Unary minus and Unary plus (Algebraic signs)	-3
~x	Bitwise negation	~3 - 4 Result: -8
**	Exponentiation	10 ** 3 Result: 1000
or, and, not	Boolean Or, Boolean And, Boolean Not	(a or b) and c
in	"Element of"	1 in [3, 2, 1]
<, <=, >, >=, !=, ==	The usual comparison operators	2 <= 3
|, &, ^	Bitwise Or, Bitwise And, Bitwise XOR	6 ^ 3
<<, >>	Shift Operators	6 << 3

Operations

Strings are bits of text. They can be defined as anything between quotes:

astring = "Hello world!"
astring2 = 'Hello world!'

Below code will prints out 12, because "Hello world!" is 12 characters long, including punctuation and spaces.

astring = "Hello world!"
print len(astring)

Below code will prints out 4, because the location of the first occurrence of the letter "o" is 4 characters away from the first character. Notice how there are actually two o's in the phrase - this method only recognizes the first.

astring = "Hello world!"
print astring.index("o")

These make a new string with all letters converted to uppercase and lowercase, respectively.

astring = "Hello world!"
print astring.upper()
print astring.lower()

Conditions

Python uses boolean variables to evaluate conditions. The boolean values True and False are returned when an expression is compared or evaluated.
For Example:

x = 2
print x == 2 # prints out True
print x == 3 # prints out False
print x < 3  # prints out True

Boolean Operators

The "and" and "or" boolean operators allow building complex boolean expressions, 
For Example:

name = "John"
age = 23
if name == "John" and age == 23:
    print "Your name is John, and you are also 23 years old."

if name == "John" or name == "Rick":
    print "Your name is either John or Rick."

True or False

Unfortunately it is not as easy in real life as it is in Python to differentiate between true and false: The following objects are evaluated by Python as False:

1. numerical zero values (0, 0L, 0.0, 0.0+0.0j),
2. the Boolean value False,
3. empty strings,
4. empty lists and empty tuples,
5. empty dictionaries.
6. plus the special value None.

All other values are considered to be True.

"In" Operator

The "in" operator could be used to check if a specified object exists within an iterable object container, such as a list:

name = "Rick"

        if name in ["John", "Rick"]:

            print "Your name is either John or Rick."
        

Python uses indentation to define code blocks, instead of brackets. The standard Python indentation is 4 spaces, although tabs and any other space size will work, as long as it is consistent. Notice that code blocks do not need any termination. 

Here is an example for using Python's "if" statement using code blocks:

if (statement is true):
 (do something)
  ....
  ....
elif (another statement is true): # else if
 (do something else)
  ....
  ....
 else:
 (do another thing)
  ....
  ....
   

Loops

There are two types of loops in Python, for and while.

"For" Loop

For loops iterate over a given sequence. Here is an example:

primes = [2, 3, 5, 7]
for prime in primes:
        print prime

The range() Function

The built-in function range() is the right function to iterate over a sequence of numbers. It generates lists of arithmetic progressions:
Example:

>>> range(10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

range(n) generates the progression of integer numbers starting with 0 and ending with (n -1)
range() can also be called with two arguments:

range(begin,end)

The above call produces the list of numbers starting with begin (inclusive) and ending with one less than the number "end".
So far the increment of range() has been 1. We can specify a different increment with a third argument. The increment is called the "step". It can be both negative and positive, but not zero:

range(begin,end, step)

for x in xrange(5): # or range(5)
    print x
# Prints out 3,4,5
for x in xrange(3, 6): # or range(3, 6)
    print x

# Prints out 3,5,7
for x in xrange(3, 8, 2): # or range(3, 8, 2)
    print x

"While" Loops

While loops repeat as long as a certain boolean condition is met.
For example:

  
 count = 0
while count < 5:
    print count
    count += 1  # This is the same as count = count + 1

The else Part

Similar to the if statement, the while loop of Python has also an optional else part. This is an unfamiliar construct for many programmers of traditional programming languages.
The statements in the else part are executed, when the condition is not fulfilled anymore. Some might ask themselves now, where the possible benefit of this extra branch is. If the statements of the additional else part were placed right after the while loop without an else, they would have been executed anyway, wouldn't they. We need to understand a new language construct, i.e. the break statement, to obtain a benefit from the additional else branch of the while loop.
The general syntax of a while loop looks like this:

while condition:
 statement_1
 ...
 statement_n
else:
 statement_1
 ...
 statement_n

"Break" and "Continue"

Break is used to exit a for loop or a while loop, whereas continue is used to skip the current block, and return to the "for" or "while" statement. A few examples:

count = 0
while True:
    print count
    count += 1
    if count >= 5:
        break

# Prints out only odd numbers - 1,3,5,7,9
for x in xrange(10):
    # Check if x is even
    if x % 2 == 0:
        continue
    print x

unlike languages like C,C++. we can use else for loops. When the loop condition of "for" or "while" statement fails then code part in "else" is executed. If break statement is executed inside for loop then the "else" part is skipped. Note that "else" part is executed even if there is a continue statement.
Here are a few examples:

count=0
while(count<5):
    print count
    count +=1
else:

    print "count value reached %d" %(count)

# Prints out 1,2,3,4
for i in xrange(1,10):
    if(i%5==0):
         break
    print i
else:<
    print "this is not printed because for loop is terminated because of break but not due to fail in condition"

Functions

What are Functions?

Functions are a construct to structure programs. They are known in most programming languages, sometimes also called subroutines or procedures. Functions are used to utilize code in more than one place in a program. The only way without functions to reuse code consists in copying the code.

A function in Python is defined by a def statement. The general syntax looks like this:

def function-name(Parameter list):
    statements, i.e. the function body
 

The parameter list consists of none or more parameters. Parameters are called arguments, if the function is called. The function body consists of indented statements. The function body gets executed every time the function is called.
Parameter can be mandatory or optional. The optional parameters (zero or more) must follow the mandatory parameters.

Function bodies can contain a return statement. It can be anywhere in the function body. This statement ends the execution of the function call and "returns" the result, i.e. the value of the expression following the return keyword, to the caller. If there is no return statement in the function code, the function ends, when the control flow reaches the end of the function body.

How do you write functions in Python?

As we have seen on previous tutorials, Python makes use of blocks. A block is a area of code of written in the format of:

block_head: 
       1st block line 
       2nd block line 
        ...
 #sample function definition
 def my_function():
        print "Hello From My Function!"

Example of a Function with Optional Parameters

>>> def add(x, y=5):
...     """Return x plus y, optional"""
...     return x + y
... 
>>> 

Calls to this function could look like this:

>>> add(4)
9
>>> add(8,3)
11
>>> 

Docstring

The first statement in the body of a function is usually a string, which can be accessed with function_name.__doc__
This statement is called Docstring.
Example:

>>> execfile("function1.py")
>>> add.__doc__
'Returns x plus y'
>>> add2.__doc__
'Returns x plus y, optional'
>>>

Keyword Parameters

Using keyword parameters is an alternative way to make function calls. The definition of the function doesn't change.
An example:

def sumsub(a, b, c=0, d=0):
    return a - b + c - d
 

Keyword parameters can only be those, which are not used as positional arguments.

>>> execfile("funktion1.py")
>>> sumsub(12,4)
8
>>> sumsub(12,4,27,23)
12
>>> sumsub(12,4,d=27,c=23)
4

Arbitrary Number of Parameters

There are many situations in programming, in which the exact number of necessary parameters cannot be determined a-priori. An arbitrary parameter number can be accomplished in Python with so-called tuple references. An asterisk "*" is used in front of the last parameter name to denote it as a tuple reference. This asterisk shouldn't be mistaken with the C syntax, where this notation is connected with pointers.
Example:

def arbitrary(x, y, *more):
    print "x=", x, ", y=", y 
    print "arbitrary: ", more
 

x and y are regular positional parameters in the previous function. *more is a tuple reference.
Example:

>>> execfile("funktion1.py")
>>> arbitrary(3,4)
x= 3 , x= 4
arbitrary:  ()
>>> arbitrary(3,4, "Hello World", 3 ,4)
x= 3 , x= 4
arbitrary:  ('Hello World', 3, 4)

Recursion

Recursion is a way of programming or coding a problem, in which a function calls itself one or more times in its body. Usually, it is returning the return value of this function call. If a function definition fulfils the condition of recursion, we call this function a recursive function. 

Termination condition:
A recursive function has to terminate to be used in a program. A recursive function terminates, if with every recursive call the solution of the problem is downsized and moves towards a base case. A base case is a case, where the problem can be solved without further recursion. A recursion can lead to an infinite loop, if the base case is not met in the calls. 

Example: 

4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1

Replacing the calculated values gives us the following expression 

4! = 4 * 3 * 2 * 1

Generally we can say: Recursion in computer science is a method where the solution to a problem is based on solving smaller instances of the same problem. 

Recursive Functions in Python

Now we come to implement the factorial in Python. It's as easy and elegant as the mathematical definition.

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)
  

We can track how the function works by adding two print() functions to the previous function definition:

def factorial(n):
    print("factorial has been called with n = " + str(n))
    if n == 1:
        return 1
    else:
        res = n * factorial(n-1)
        print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res)
        return res 

print(factorial(5))

This Python script outputs the following results:

factorial has been called with n = 5
factorial has been called with n = 4
factorial has been called with n = 3
factorial has been called with n = 2
factorial has been called with n = 1
intermediate result for  2  * factorial( 1 ):  2
intermediate result for  3  * factorial( 2 ):  6
intermediate result for  4  * factorial( 3 ):  24
intermediate result for  5  * factorial( 4 ):  120
120

Let's have a look at an iterative version of the factorial function.

def iterative_factorial(n):
    result = 1
    for i in range(2,n+1):
        result *= i
    return result
 

The Pitfalls of Recursion

This subchapter of our tutorial on recursion deals with the Fibonacci numbers. What do have sunflowers, the Golden ratio, fur tree cones, The Da Vinci Code and the song "Lateralus" by Tool in common. Right, the Fibonacci numbers. 

The Fibonacci numbers are the numbers of the following sequence of integer values: 

0,1,1,2,3,5,8,13,21,34,55,89, ...

The Fibonacci numbers are defined by: 
Fn = Fn-1 + Fn-2 
with F0 = 0 and F1 = 1 

The Fibonacci sequence is named after the mathematician Leonardo of Pisa, who is better known as Fibonacci. In his book "Liber Abaci" (publishes 1202) he introduced the sequence as an exercise dealing with bunnies. His sequence of the Fibonacci numbers begins with F₁ = 1, while in modern mathematics the sequence starts with F₀ = 0. But this has no effect on the other members of the sequence. 

The Fibonacci numbers are the result of an artificial rabbit population, satisfying the following conditions: 

1. a newly born pair of rabbits, one male, one female, build the initial population
2. these rabbits are able to mate at the age of one month so that at the end of its second month a female can bring forth another pair of rabbits
3. these rabbits are immortal
4. a mating pair always produces one new pair (one male, one female) every month from the second month onwards

The Fibonacci numbers are the numbers of rabbit pairs after n months, i.e. after 10 months we will have F₁₀ rabbits. 

The Fibonacci numbers are easy to write as a Python function. It's more or less a one to one mapping from the mathematical definition:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
  

An iterative solution for the problem is also easy to write, though the recursive solution looks more like the mathematical definition:

def fibi(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a
 

If you check the functions fib() and fibi(), you will find out that the iterative version fibi() is a lot faster than the recursive version fib(). To get an idea of how much this "a lot faster" can be, we have written a script where we you the timeit module to measure the calls: 

from timeit import Timer
from fibo import fib

t1 = Timer("fib(10)","from fibo import fib")

for i in range(1,41):
 s = "fib(" + str(i) + ")"
 t1 = Timer(s,"from fibo import fib")
 time1 = t1.timeit(3)
 s = "fibi(" + str(i) + ")"
 t2 = Timer(s,"from fibo import fibi")
 time2 = t2.timeit(3)
 print("n=%2d, fib: %8.6f, fibi:  %7.6f, percent: %10.2f" % (i, time1, time2, time1/time2))
 

time1 is the time in seconds it takes for 3 calls to fib(n) and time2 respectively the time for fibi(). If we look at the results, we can see that calling fib(20) three times needs about 14 milliseconds. fibi(20) needs just 0.011 milliseconds for 3 calls. So fibi(20) is about 1300 times faster then fib(20). 
fib(40) needs already 215 seconds for three calls, while fibi(40) can do it in 0.016 milliseconds. fibi(40) is more than 13 millions times faster than fib(40). 

n= 1, fib: 0.000004, fibi:  0.000005, percent:       0.81
n= 2, fib: 0.000005, fibi:  0.000005, percent:       1.00
n= 3, fib: 0.000006, fibi:  0.000006, percent:       1.00
n= 4, fib: 0.000008, fibi:  0.000005, percent:       1.62
n= 5, fib: 0.000013, fibi:  0.000006, percent:       2.20
n= 6, fib: 0.000020, fibi:  0.000006, percent:       3.36
n= 7, fib: 0.000030, fibi:  0.000006, percent:       5.04
n= 8, fib: 0.000047, fibi:  0.000008, percent:       5.79
n= 9, fib: 0.000075, fibi:  0.000007, percent:      10.50
n=10, fib: 0.000118, fibi:  0.000007, percent:      16.50
n=11, fib: 0.000198, fibi:  0.000007, percent:      27.70
n=12, fib: 0.000287, fibi:  0.000007, percent:      41.52
n=13, fib: 0.000480, fibi:  0.000007, percent:      69.45
n=14, fib: 0.000780, fibi:  0.000007, percent:     112.83
n=15, fib: 0.001279, fibi:  0.000008, percent:     162.55
n=16, fib: 0.002059, fibi:  0.000009, percent:     233.41
n=17, fib: 0.003439, fibi:  0.000011, percent:     313.59
n=18, fib: 0.005794, fibi:  0.000012, percent:     486.04
n=19, fib: 0.009219, fibi:  0.000011, percent:     840.59
n=20, fib: 0.014366, fibi:  0.000011, percent:    1309.89
n=21, fib: 0.023137, fibi:  0.000013, percent:    1764.42
n=22, fib: 0.036963, fibi:  0.000013, percent:    2818.80
n=23, fib: 0.060626, fibi:  0.000012, percent:    4985.96
n=24, fib: 0.097643, fibi:  0.000013, percent:    7584.17
n=25, fib: 0.157224, fibi:  0.000013, percent:   11989.91
n=26, fib: 0.253764, fibi:  0.000013, percent:   19352.05
n=27, fib: 0.411353, fibi:  0.000012, percent:   34506.80
n=28, fib: 0.673918, fibi:  0.000014, percent:   47908.76
n=29, fib: 1.086484, fibi:  0.000015, percent:   72334.03
n=30, fib: 1.742688, fibi:  0.000014, percent:  123887.51
n=31, fib: 2.861763, fibi:  0.000014, percent:  203442.44
n=32, fib: 4.648224, fibi:  0.000015, percent:  309461.33
n=33, fib: 7.339578, fibi:  0.000014, percent:  521769.86
n=34, fib: 11.980462, fibi:  0.000014, percent:  851689.83
n=35, fib: 19.426206, fibi:  0.000016, percent: 1216110.64
n=36, fib: 30.840097, fibi:  0.000015, percent: 2053218.13
n=37, fib: 50.519086, fibi:  0.000016, percent: 3116064.78
n=38, fib: 81.822418, fibi:  0.000015, percent: 5447430.08
n=39, fib: 132.030006, fibi:  0.000018, percent: 7383653.09
n=40, fib: 215.091484, fibi:  0.000016, percent: 13465060.78

What's wrong with our recursive implementation?

Let's have a look at the calculation tree, i.e. the order in which the functions are called. fib() is substituted by fib(). 



We can see that the subtree f(2) appears 3 times and the subtree for the calculation of f(3) two times. If you imagine extending this tree for f(6), you will understand that f(4) will be called two times, f(3) three times and so on. This means, our recursion doesn't remember previously calculated values. 

We can implement a "memory" for our recursive version by using a dictionary to save the previously calculated values.

memo = {0:0, 1:1}
def fibm(n):
    if not n in memo:
        memo[n] = fibm(n-1) + fibm(n-2)
    return memo[n]
 

We time it again to compare it with fibi():

from timeit import Timer
from fibo import fib

t1 = Timer("fib(10)","from fibo import fib")

for i in range(1,41):
 s = "fibm(" + str(i) + ")"
 t1 = Timer(s,"from fibo import fibm")
 time1 = t1.timeit(3)
 s = "fibi(" + str(i) + ")"
 t2 = Timer(s,"from fibo import fibi")
 time2 = t2.timeit(3)
 print("n=%2d, fib: %8.6f, fibi:  %7.6f, percent: %10.2f" % (i, time1, time2, time1/time2))
 

We can see that it is even faster than the iterative version. Of course, the larger the arguments the greater the benefit of our memoisation: 

n= 1, fib: 0.000011, fibi:  0.000015, percent:       0.73
n= 2, fib: 0.000011, fibi:  0.000013, percent:       0.85
n= 3, fib: 0.000012, fibi:  0.000014, percent:       0.86
n= 4, fib: 0.000012, fibi:  0.000015, percent:       0.79
n= 5, fib: 0.000012, fibi:  0.000016, percent:       0.75
n= 6, fib: 0.000011, fibi:  0.000017, percent:       0.65
n= 7, fib: 0.000012, fibi:  0.000017, percent:       0.72
n= 8, fib: 0.000011, fibi:  0.000018, percent:       0.61
n= 9, fib: 0.000011, fibi:  0.000018, percent:       0.61
n=10, fib: 0.000010, fibi:  0.000020, percent:       0.50
n=11, fib: 0.000011, fibi:  0.000020, percent:       0.55
n=12, fib: 0.000004, fibi:  0.000007, percent:       0.59
n=13, fib: 0.000004, fibi:  0.000007, percent:       0.57
n=14, fib: 0.000004, fibi:  0.000008, percent:       0.52
n=15, fib: 0.000004, fibi:  0.000008, percent:       0.50
n=16, fib: 0.000003, fibi:  0.000008, percent:       0.39
n=17, fib: 0.000004, fibi:  0.000009, percent:       0.45
n=18, fib: 0.000004, fibi:  0.000009, percent:       0.45
n=19, fib: 0.000004, fibi:  0.000009, percent:       0.45
n=20, fib: 0.000003, fibi:  0.000010, percent:       0.29
n=21, fib: 0.000004, fibi:  0.000009, percent:       0.45
n=22, fib: 0.000004, fibi:  0.000010, percent:       0.40
n=23, fib: 0.000004, fibi:  0.000010, percent:       0.40
n=24, fib: 0.000004, fibi:  0.000011, percent:       0.35
n=25, fib: 0.000004, fibi:  0.000012, percent:       0.33
n=26, fib: 0.000004, fibi:  0.000011, percent:       0.34
n=27, fib: 0.000004, fibi:  0.000011, percent:       0.35
n=28, fib: 0.000004, fibi:  0.000012, percent:       0.32
n=29, fib: 0.000004, fibi:  0.000012, percent:       0.33
n=30, fib: 0.000004, fibi:  0.000013, percent:       0.31
n=31, fib: 0.000004, fibi:  0.000012, percent:       0.34
n=32, fib: 0.000004, fibi:  0.000012, percent:       0.33
n=33, fib: 0.000004, fibi:  0.000013, percent:       0.30
n=34, fib: 0.000004, fibi:  0.000012, percent:       0.34
n=35, fib: 0.000004, fibi:  0.000013, percent:       0.31
n=36, fib: 0.000004, fibi:  0.000013, percent:       0.31
n=37, fib: 0.000004, fibi:  0.000014, percent:       0.29
n=38, fib: 0.000004, fibi:  0.000014, percent:       0.29
n=39, fib: 0.000004, fibi:  0.000013, percent:       0.31
n=40, fib: 0.000004, fibi:  0.000014, percent:       0.29