Iteration and Recursion:

Conditional execution

The ability to check conditions and change the behaviour of the program accordingly.

Conditional statements give us this ability.

The simplest form is the if statement:

if x > 0:

print 'x is positive'

The boolean expression after if is called the condition. If it is true, then the indented statement gets executed. If not, nothing happens.

In compound statements There is no limit on the number of statements that can appear in the body. ===============================================================

Alternative execution

If statement is alternative execution, in which there are two possibilities and the condition determines which one gets executed.

The syntax looks like this:

if x%2 == 0:

print 'x is even'

else:

print 'x is odd'

If the condition is false, the second set of statements is executed. The condition must be true or false, exactly one of the alternatives will be executed.

The alternatives are called branches, because they are branches in the flow of execution.

==============================================

Chained conditionals

More than two possibilities and we need more than two branches.

One way to express a computation like that is a chained conditional:

if x < y:

print 'x is less than y'

elif x > y:

print 'x is greater than y'

else:

print 'x and y are equal'

elif is an abbreviation of “else if.” one branch will be executed. There is no limit on the number of elif statements. If there is an else clause, it has to be at the end, but there doesn’t have to be one.

if choice == 'a':

draw_a()

elif choice == 'b':

draw_b()

elif choice == 'c':

draw_c()

Each condition is checked in order. If the first is false, the next is checked, and so on. If one of them is true, the corresponding branch executes, and the statement ends. Even if more than one condition is true, only the first true branch executes.

============================================

Nested conditionals

One conditional can also be nested within another. We could have written the trichotomy

example:

if x == y:

print 'x and y are equal'

else:

if x < y:

print 'x is less than y'

else:

print 'x is greater than y'

The outer conditional contains two branches. The first branch contains a simple statement. The second branch contains another if statement, which has two branches of its own. Those two branches are both simple statements, although they could have been conditional statements as well.

The indentation of the statements makes the structure apparent, nested conditionals become difficult to read very quickly.

Logical operators often provide a way to simplify nested conditional statements.

Example:-

We can rewrite the following code using a single conditional:

if 0 < x:

if x < 10:

print 'x is a positive single-digit number.'

The print statement is executed only if we make it past both conditionals, so we can get the same effect with the and operator:

if 0 < x and x < 10:

print 'x is a positive single-digit number.'

============================================

Recursion

Recursion is the process of defining or call itself.

Example:- two parallel mirrors facing each other. Any object in between them would be reflected recursively.

It is a common mathematical and programming concept. you can loop through data to reach a result.

Example :-  find the factorial of an integer.

Factorial of a number is the product of all the integers from 1 to that number. For example, the factorial of 6 (denoted as 6!) is 1*2*3*4*5*6 = 720.

Example of a recursive function

def factorial(x):

    to find the factorial of an integer"""

    if x == 1:

        return 1

    else:

        return (x * factorial(x-1))

num = 3

print("The factorial of", num, "is", factorial(num))

Output

The factorial of 3 is 6

When we call this function with a positive integer, it will recursively call itself by decreasing the number.

Each function multiplies the number with the factorial of the number below it until it is equal to one.

The Fibonacci numbers were originally defined by the Italian mathematician Fibonacci in the thirteenth century to model the growth of rabbit populations.

F_n = F_n-1 + F_n-2

The base cases are:

F₀ = 0 and F₁ = 1

Example :- To compute the nth Fibonacci number:

def fibonacci_recursive(n):

    print("Calculating F", "(", n, ")", sep="", end=", ")

    # Base case

    if n == 0:

        return 0

    elif n == 1:

        return 1

    # Recursive case

    else:

        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

>>> fibonacci_recursive(5)

Calculating F(5), Calculating F(4), Calculating F(3), Calculating F(2), Calculating F(1),

Calculating F(0), Calculating F(1), Calculating F(2), Calculating F(1), Calculating F(0),

Calculating F(3), Calculating F(2), Calculating F(1), Calculating F(0), Calculating F(1),

=======================================================

Advantages of Recursion

·         Easier to write.

·         Readable – Code is easier to read, clean and elegant and understand.

·         Reduce the lines of code – It takes less lines of code to solve a problem using recursion.

·         A complex task can be broken down into simpler sub-problems using recursion.

• Sequence generation is easier with recursion than using some nested iteration.

---

Disadvantages of Recursion

1. Sometimes the logic behind recursion is hard to follow through.
2. Recursive calls are expensive (inefficient) as they take up a lot of memory and time.
3. Recursive functions are hard to debug.
4. Not all problems can be solved using recursion.
5. If you don’t define the base case then the code would run indefinitely.

================================================

Simultaneous Assignments

Python allow simultaneous assignment syntax like this:

var1, var2, ..., varn = exp1, exp2, ..., expn

This statements tells the python to evaluate all the expression on the right and assign them to the corresponding variables on the left.

Example:- Simultaneous Assignments is helpful to swap values of two variables.

>>> x = 1

>>> y = 2

>>> y, x = x, y # assign y value to x and x value to y

==============================================

Stack diagrams for recursive functions

In the recursive function, there might be more than one frame on the stack at the same time.

A stack diagram for countdown called with n = 3.

The top of the stack is the frame for __main__. It is empty because we did not create any variables in __main__ or pass any arguments to it.

The four countdown frames have different values for the parameter n.

The bottom of the stack, where n=0, is called the base case. It does not make a recursive call, so there are no more frames.

Exercise . Write a function called do_n that takes a function object and a number, n, as arguments, and that calls the given function n times.Stack diagram :-

In stack a stack diagram to represent the state of a program during a function call.

The same kind of diagram can help interpret a recursive function.

Every time a function gets called, Python creates a new function frame, which contains the function’s local variables and parameters. For a recursive function, there might be more than one frame on the stack at the same time.

================================================================

The while statement

Computers are often used to automate repetitive tasks. Repeating identical or similar tasks

without making errors is something that two programs, countdown and print_n, that use recursion to perform repetition,

Which is also called iteration. Because iteration is so common.

Python provides several language features to make it easier. One is the for statement and Another is the while statement.

Uses a while statement:

def countdown(n):

while n > 0:

print n

n = n-1

print ‘hello’

The flow of execution for a while statement:

1. Evaluate the condition, yielding True or False.
2. If the condition is false, exit the while statement and continue execution at the next statement.
3. If the condition is true, execute the body and then go back to step 1.

This type of flow is called a loop because the third step loops back around to the top.

The body of the loop should change the value of one or more variables so that eventually the condition becomes false and the loop terminates. Otherwise the loop will repeat forever, which is called an infinite loop.

In the case of countdown, we can prove that the loop terminates because we know that the value of n is finite, and we can see that the value of n gets smaller each time through the loop, so eventually we have to get to 0.

Example:-

def sequence(n):

while n != 1:

print n,

if n%2 == 0: # n is even

n = n/2

else: # n is odd

n = n*3+1

The condition for this loop is n != 1, so the loop will continue until n is 1, which makes the condition false.

Each time through the loop, the program outputs the value of n and then checks whether it is even or odd. If it is even, n is divided by 2. If it is odd, the value of n is replaced with n*3+1.

===========================================

Implementing 2-D matrices

A matrix is a two-dimensional data structure where numbers are arranged into rows and columns. For example:

This matrix is a 3x4 (pronounced "three by four") matrix because it has 3 rows and 4 columns.

Declaration of a 2-D Array

Syntax:

array-name = [ [d1, d2, .... dn], [e1, e2, .... en] ]

---

Input to a 2-D Array

Input to a 2-D array is provided in the form of rows and columns.

Example:

size = int(input("enter the size of arrey :- ")) print("enter the array values :- ") array_input = [] for x in range(size):     array_input.append([int(y) for y in input().split()]) print("result of ", array_input)

Output:

2

1 2 3 4

5 6 7 8

[[1,2,3,4], [5,6,7,8]]

=================================

Accessing Values in a Two Dimensional Array

The data elements in two dimensional arrays can be accessed using two indices. One index referring to the main or parent array and another index referring to the position of the data element in the inner array.

If we mention only one index then the entire inner array is printed for that index position.

Example :- .

from array import *

T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]]

print(T[0])

print(T[1][2])

Output :- −

[11, 12, 5, 2]

10

Ex.:-

from array import *

T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]]

for r in T:

    for c in r:

        print(c,end = " ")

    print()

Result −

11 12 5 2 

15 6 10 

10 8 12 5 

12 15 8 6 

 

Inserting Values in Two Dimensional Array

We can insert new data elements at specific position by using the insert() method and specifying the index.

Elements in a 2D array can be inserted using the insert() function specifying the index/position of the element to be inserted.

from array import * input = [[1,1,1,1], [12,12,12,12]] print("Array before insertion of elements: ") print(input)   input.insert(1, [1,3,5,7,9]) print("Array after insertion of elements: ") for x in input:      for y in x:          print(y,end = " ")      print()

Output:

Array before insertion of elements:

[[1, 1, 1, 1], [12, 12, 12, 12]]

Array after insertion of elements:

1 1 1 1

1 3 5 7 9

12 12 12 12

===========================

Updating Values in Two Dimensional Array

We can update the entire inner array or some specific data elements of the inner array by reassigning the values using the array index.

from array import * input = [[1,1,1,1], [12,12,12,12]] print("Array before Updation of elements: ") print(input)   input[0] = [10,8] input[1][1] = 9 print("Array after updation of elements: ") for x in input:      for y in x:          print(y,end = " ")      print()

Output:

Array before Updation of elements:

[[1, 1, 1, 1], [12, 12, 12, 12]]

Array after updation of elements:

10 8

12 9 12 12

Deleting the Values in Two Dimensional Array

We can delete the entire inner array or some specific data elements of the inner array by reassigning the values using the del() method with index. But in case you need to remove specific data elements in one of the inner arrays, then use the update process.

Delete values from a 2-D array

The elements from a 2-D array can be deleted using del() method.

from array import * input = [[1,1,1,1], [12,12,12,12], [0,2]] print("Array before Deletion of elements: ") print(input)   del(input[1]) print("Array after Deletion of elements: ") for x in input:      for y in x:          print(y,end = " ")      print()

Output:

Array before Deletion of elements:

[[1, 1, 1, 1], [12, 12, 12, 12], [0, 2]]

Array after Deletion of elements:

1 1 1 1

0 2

---

Size of a 2-D array

The length of an array can be determined using the len() method.

array_input = [[3,9],[0,3,7,10]] print(len(array_input))

Output:

2

---

2-D array Append

The elements can be appended to an array using the append() method. The element gets added to the end of the array.

from array import * input = [[1,1,1,1], [12,12,12,12], [0,2]] print("Array before appending the elements: ") print(input)   input.append([1,2]) print("Array after appending of the elements: ") for x in input:      for y in x:          print(y,end = " ")      print()

Output:

Array before appending the elements:

[[1, 1, 1, 1], [12, 12, 12, 12], [0, 2]]

Array after appending of the elements:

1 1 1 1

12 12 12 12

0 2

1 2

---

 

Slicing of a 2-D array in Python

Array slicing is used to access multiple values within an array.

Syntax:

<slice_array> = <array>[start:stop]

array1 = [[1,2,3],[4,5,6,7]]   #python array slice   array2 = array1[1:3] #index 1 to 2 print(array2)   array2 = array1[:1] #index 0 to 1 print(array2)

Output:

[[4, 5, 6, 7]]

[[1, 2, 3]]

We can perform matrix addition in various ways in Python.

 

Matrix Addition using Nested Loop

# Program to add two matrices using nested loop

X = [[12,7,3],

    [4 ,5,6],

    [7 ,8,9]]

Y = [[5,8,1],

    [6,7,3],

    [4,5,9]]

result = [[0,0,0],

         [0,0,0],

         [0,0,0]]

# iterate through rows

for i in range(len(X)):

   # iterate through columns

   for j in range(len(X[0])):

       result[i][j] = X[i][j] + Y[i][j]

for r in result:

   print(r)

Output

[17, 15, 4]

[10, 12, 9]

[11, 13, 18]

In this program we have used nested for loops to iterate through each row and each column. At each point, we add the corresponding elements in the two matrices and store it in the result.

 

Matrix Addition using Nested List Comprehension

# Program to add two matrices using list comprehension

X = [[12,7,3],

    [4 ,5,6],

    [7 ,8,9]]

Y = [[5,8,1],

    [6,7,3],

    [4,5,9]]

result = [[X[i][j] + Y[i][j]  for j in range(len(X[0]))] for i in range(len(X))]

for r in result:

   print(r)

The output of this program is the same as above. We have used nested list comprehension to iterate through each element in the matrix.

Transpose of a matrix is the interchanging of rows and columns.

It is denoted as X'. The element at ith row and jth column in X will be placed at jth row and ith column in X'. So if X is a 3x2 matrix, X' will be a 2x3 matrix.

Here are a couple of ways to accomplish this in Python.

Matrix Transpose using Nested Loop

# Program to transpose a matrix using a nested loop

X = [[12,7],

    [4 ,5],

    [3 ,8]]

result = [[0,0,0],

         [0,0,0]]

# iterate through rows

for i in range(len(X)):

   # iterate through columns

   for j in range(len(X[0])):

       result[j][i] = X[i][j]

for r in result:

   print(r)

Output

[12, 4, 3]

[7, 5, 8]

In this program, we have used nested for loops to iterate through each row and each column. At each point we place the X[i][j] element into result[j][i].

---

Matrix Transpose using Nested List Comprehension

''' Program to transpose a matrix using list comprehension'''

X = [[12,7],

    [4 ,5],

    [3 ,8]]

result = [[X[j][i] for j in range(len(X))] for i in range(len(X[0]))]

for r in result:

   print(r)

output:- 

[12, 4, 3]

[7, 5, 8]

The output of this program is the same as above. We have used nested list comprehension to iterate through each element in the matrix.

Multiplication of two matrices

 X and Y is defined only if the number of columns in X is equal to the number of rows Y.

If X is a n x m matrix and Y is a m x l matrix then, XY is defined and has the dimension n x l (but YX is not defined). Here are a couple of ways to implement matrix multiplication in Python.

Matrix Multiplication using Nested Loop

# Program to multiply two matrices using nested loops

# 3x3 matrix

X = [[12,7,3],

    [4 ,5,6],

    [7 ,8,9]]

# 3x4 matrix

Y = [[5,8,1,2],

    [6,7,3,0],

    [4,5,9,1]]

# result is 3x4

result = [[0,0,0,0],

         [0,0,0,0],

         [0,0,0,0]]

# iterate through rows of X

for i in range(len(X)):

   # iterate through columns of Y

   for j in range(len(Y[0])):

       # iterate through rows of Y

       for k in range(len(Y)):

           result[i][j] += X[i][k] * Y[k][j]

for r in result:

   print(r)

Output

[114, 160, 60, 27]

[74, 97, 73, 14]

[119, 157, 112, 23]

In this program, we have used nested for loops to iterate through each row and each column. We accumulate the sum of products in the result.

This technique is simple but computationally expensive as we increase the order of the matrix.

For larger matrix operations we recommend optimized software packages like NumPy which is several (in the order of 100) times faster than the above code.

Matrix Multiplication Using Nested List Comprehension

# Program to multiply two matrices using list comprehension

# 3x3 matrix

X = [[12,7,3],

    [4 ,5,6],

    [7 ,8,9]]

# 3x4 matrix

Y = [[5,8,1,2],

    [6,7,3,0],

    [4,5,9,1]]

# result is 3x4

result = [[sum(a*b for a,b in zip(X_row,Y_col)) for Y_col in zip(*Y)] for X_row in X]

for r in result:

   print(r) 

output:- 

[114, 160, 60, 27]

[74, 97, 73, 14]

[119, 157, 112, 23]

=========================*******************************=========